From 0a9d51ee9d2b3d0111832e5ea1c8195a16e2f99b Mon Sep 17 00:00:00 2001 From: Hiroshi SHIBATA Date: Sat, 12 Nov 2022 06:00:58 +0900 Subject: Migrate our resolver engine to PubGrub MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit https://github.com/rubygems/rubygems/pull/5960 Co-authored-by: David Rodríguez --- lib/bundler/resolver.rb | 492 +++++++++++++++++++++++------------------------- 1 file changed, 234 insertions(+), 258 deletions(-) (limited to 'lib/bundler/resolver.rb') diff --git a/lib/bundler/resolver.rb b/lib/bundler/resolver.rb index 115c5cfcc4..07607813ec 100644 --- a/lib/bundler/resolver.rb +++ b/lib/bundler/resolver.rb @@ -1,81 +1,128 @@ # frozen_string_literal: true module Bundler + # + # This class implements the interface needed by PubGrub for resolution. It is + # equivalent to the `PubGrub::BasicPackageSource` class provided by PubGrub by + # default and used by the most simple PubGrub consumers. + # class Resolver - require_relative "vendored_molinillo" + require_relative "vendored_pub_grub" require_relative "resolver/base" - require_relative "resolver/spec_group" + require_relative "resolver/package" + require_relative "resolver/candidate" + require_relative "resolver/root" include GemHelpers - def initialize(source_requirements, base, gem_version_promoter, additional_base_requirements, platforms) + def initialize(source_requirements, base, gem_version_promoter, additional_base_requirements) @source_requirements = source_requirements @base = Resolver::Base.new(base, additional_base_requirements) - @resolver = Molinillo::Resolver.new(self, self) - @results_for = {} - @search_for = {} - @platforms = platforms - @resolving_only_for_ruby = platforms == [Gem::Platform::RUBY] @gem_version_promoter = gem_version_promoter end - def start(requirements, exclude_specs: []) - @metadata_requirements, regular_requirements = requirements.partition {|dep| dep.name.end_with?("\0") } - + def start(requirements, packages, exclude_specs: []) exclude_specs.each do |spec| remove_from_candidates(spec) end - requirements.each {|dep| prerelease_specified[dep.name] ||= dep.prerelease? } + root = Resolver::Root.new(name_for_explicit_dependency_source) + root_version = Resolver::Candidate.new(0) + + @sorted_versions = Hash.new do |candidates, package| + candidates[package] = if package.root? + [root_version] + else + all_versions_for(package).sort + end + end + + root_dependencies = prepare_dependencies(requirements, packages) + + @cached_dependencies = Hash.new do |dependencies, package| + dependencies[package] = if package.root? + { root_version => root_dependencies } + else + Hash.new do |versions, version| + versions[version] = to_dependency_hash(version.dependencies, packages) + end + end + end + + logger = Bundler::UI::Shell.new + logger.level = debug? ? "debug" : "warn" + solver = PubGrub::VersionSolver.new(:source => self, :root => root, :logger => logger) + before_resolution + result = solver.solve + after_resolution + result.map {|package, version| version.to_specs(package) }.flatten.uniq + rescue PubGrub::SolveFailure => e + incompatibility = e.incompatibility + + names_to_unlock = [] + conflict_on_bundler = nil + + while incompatibility.conflict? + cause = incompatibility.cause + incompatibility = cause.incompatibility - verify_gemfile_dependencies_are_found!(requirements) - result = @resolver.resolve(requirements). - map(&:payload). - reject {|sg| sg.name.end_with?("\0") }. - map(&:to_specs). - flatten + incompatibility.terms.each do |term| + name = term.package.name + names_to_unlock << name if base_requirements[name] + next unless name == "bundler" - SpecSet.new(SpecSet.new(result).for(regular_requirements, false, @platforms)) - rescue Molinillo::VersionConflict => e - conflicts = e.conflicts + no_versions_incompat = [cause.incompatibility, cause.satisfier].find {|incompat| incompat.cause.is_a?(PubGrub::Incompatibility::NoVersions) } + next unless no_versions_incompat - deps_to_unlock = conflicts.values.inject([]) do |deps, conflict| - deps |= conflict.requirement_trees.flatten.map {|req| base_requirements[req.name] }.compact + conflict_on_bundler ||= Gem::Requirement.new(no_versions_incompat.cause.constraint.constraint.constraint_string.split(",")) + end end - if deps_to_unlock.any? - @base.unlock_deps(deps_to_unlock) - reset_spec_cache + if names_to_unlock.any? + @base.unlock_names(names_to_unlock) retry end - message = version_conflict_message(e) - raise VersionConflict.new(conflicts.keys.uniq, message) - rescue Molinillo::CircularDependencyError => e - names = e.dependencies.sort_by(&:name).map {|d| "gem '#{d.name}'" } - raise CyclicDependencyError, "Your bundle requires gems that depend" \ - " on each other, creating an infinite loop. Please remove" \ - " #{names.count > 1 ? "either " : ""}#{names.join(" or ")}" \ - " and try again." + explanation = e.message + + if conflict_on_bundler + explanation << "\n\n" + explanation << bundler_not_found_message(conflict_on_bundler) + end + + raise SolveFailure.new(explanation) + end + + def parse_dependency(package, dependency) + range = if repository_for(package).is_a?(Source::Gemspec) + PubGrub::VersionRange.any + else + requirement_to_range(dependency) + end + + PubGrub::VersionConstraint.new(package, :range => range) end - include Molinillo::UI - - # Conveys debug information to the user. - # - # @param [Integer] depth the current depth of the resolution process. - # @return [void] - def debug(depth = 0) - return unless debug? - debug_info = yield - debug_info = debug_info.inspect unless debug_info.is_a?(String) - puts debug_info.split("\n").map {|s| depth == 0 ? "BUNDLER: #{s}" : "BUNDLER(#{depth}): #{s}" } + def versions_for(package, range=VersionRange.any) + versions = range.select_versions(@sorted_versions[package]) + + sort_versions(package, versions) + end + + def no_versions_incompatibility_for(package, unsatisfied_term) + cause = PubGrub::Incompatibility::NoVersions.new(unsatisfied_term) + + custom_explanation = if package.name == "bundler" + "the current Bundler version (#{Bundler::VERSION}) does not satisfy #{cause.constraint}" + else + "#{cause.constraint} could not be found in #{repository_for(package)}" + end + + PubGrub::Incompatibility.new([unsatisfied_term], :cause => cause, :custom_explanation => custom_explanation) end def debug? - return @debug_mode if defined?(@debug_mode) - @debug_mode = - ENV["BUNDLER_DEBUG_RESOLVER"] || + ENV["BUNDLER_DEBUG_RESOLVER"] || ENV["BUNDLER_DEBUG_RESOLVER_TREE"] || ENV["DEBUG_RESOLVER"] || ENV["DEBUG_RESOLVER_TREE"] || @@ -90,63 +137,87 @@ module Bundler Bundler.ui.info "" end - def indicate_progress - Bundler.ui.info ".", false unless debug? - end + def incompatibilities_for(package, version) + package_deps = @cached_dependencies[package] + sorted_versions = @sorted_versions[package] + package_deps[version].map do |dep_package, dep_constraint| + unless dep_constraint + # falsey indicates this dependency was invalid + cause = PubGrub::Incompatibility::InvalidDependency.new(dep_package, dep_constraint.constraint_string) + return [PubGrub::Incompatibility.new([PubGrub::Term.new(self_constraint, true)], :cause => cause)] + end - include Molinillo::SpecificationProvider + low = high = sorted_versions.index(version) - def dependencies_for(specification) - specification.dependencies_for_activated_platforms - end + # find version low such that all >= low share the same dep + while low > 0 && package_deps[sorted_versions[low - 1]][dep_package] == dep_constraint + low -= 1 + end + low = + if low == 0 + nil + else + sorted_versions[low] + end - def search_for(dependency) - @search_for[dependency] ||= begin - name = dependency.name - locked_results = @base[name].select {|spec| requirement_satisfied_by?(dependency, nil, spec) } - locked_requirement = base_requirements[name] - results = results_for(dependency) + locked_results - results = results.select {|spec| requirement_satisfied_by?(locked_requirement, nil, spec) } if locked_requirement - dep_platforms = dependency.gem_platforms(@platforms) - - @gem_version_promoter.sort_versions(dependency, results).group_by(&:version).reduce([]) do |groups, (_, specs)| - relevant_platforms = dep_platforms.select {|platform| specs.any? {|spec| spec.match_platform(platform) } } - next groups unless relevant_platforms.any? - - ruby_specs = select_best_platform_match(specs, Gem::Platform::RUBY) - if ruby_specs.any? - spec_group_ruby = SpecGroup.new(ruby_specs, [Gem::Platform::RUBY]) - spec_group_ruby.force_ruby_platform = dependency.force_ruby_platform - groups << spec_group_ruby + # find version high such that all < high share the same dep + while high < sorted_versions.length && package_deps[sorted_versions[high]][dep_package] == dep_constraint + high += 1 + end + high = + if high == sorted_versions.length + nil + else + sorted_versions[high] end - next groups if @resolving_only_for_ruby || dependency.force_ruby_platform + range = PubGrub::VersionRange.new(:min => low, :max => high, :include_min => true) - platform_specs = relevant_platforms.flat_map {|platform| select_best_platform_match(specs, platform) } - next groups if platform_specs == ruby_specs + self_constraint = PubGrub::VersionConstraint.new(package, :range => range) - spec_group = SpecGroup.new(platform_specs, relevant_platforms) - groups << spec_group + dep_term = PubGrub::Term.new(dep_constraint, false) - groups + custom_explanation = if dep_package.meta? && package.root? + "current #{dep_package} version is #{dep_constraint.constraint_string}" end + + PubGrub::Incompatibility.new([PubGrub::Term.new(self_constraint, true), dep_term], :cause => :dependency, :custom_explanation => custom_explanation) + end + end + + def all_versions_for(package) + name = package.name + results = @base[name] + results_for(name) + locked_requirement = base_requirements[name] + results = results.select {|spec| requirement_satisfied_by?(locked_requirement, spec) } if locked_requirement + + versions = results.group_by(&:version).reduce([]) do |groups, (version, specs)| + platform_specs = package.platforms.flat_map {|platform| select_best_platform_match(specs, platform) } + next groups if platform_specs.empty? + + ruby_specs = select_best_platform_match(specs, Gem::Platform::RUBY) + groups << Resolver::Candidate.new(version, :specs => ruby_specs) if ruby_specs.any? + + next groups if platform_specs == ruby_specs + + groups << Resolver::Candidate.new(version, :specs => platform_specs) + + groups end + + sort_versions(package, versions) end - def index_for(dependency) - source_for(dependency.name).specs + def index_for(name) + source_for(name).specs end def source_for(name) @source_requirements[name] || @source_requirements[:default] end - def results_for(dependency) - @results_for[dependency] ||= index_for(dependency).search(dependency) - end - - def name_for(dependency) - dependency.name + def results_for(name) + index_for(name).search(name) end def name_for_explicit_dependency_source @@ -155,107 +226,66 @@ module Bundler "Gemfile" end - def requirement_satisfied_by?(requirement, activated, spec) - requirement.matches_spec?(spec) || spec.source.is_a?(Source::Gemspec) + def requirement_satisfied_by?(requirement, spec) + requirement.satisfied_by?(spec.version) || spec.source.is_a?(Source::Gemspec) end - def sort_dependencies(dependencies, activated, conflicts) - dependencies.sort_by do |dependency| - name = name_for(dependency) - vertex = activated.vertex_named(name) - [ - @base[name].any? ? 0 : 1, - vertex.payload ? 0 : 1, - vertex.root? ? 0 : 1, - amount_constrained(dependency), - conflicts[name] ? 0 : 1, - vertex.payload ? 0 : search_for(dependency).count, - ] + private + + def sort_versions(package, versions) + if versions.size > 1 + @gem_version_promoter.sort_versions(package, versions).reverse + else + versions end end - private + def repository_for(package) + source_for(package.name) + end def base_requirements @base.base_requirements end - def prerelease_specified - @gem_version_promoter.prerelease_specified - end - def remove_from_candidates(spec) @base.delete(spec) - - @results_for.keys.each do |dep| - next unless dep.name == spec.name - - @results_for[dep].reject {|s| s.name == spec.name && s.version == spec.version } - end - - reset_spec_cache - end - - def reset_spec_cache - @search_for = {} - @gem_version_promoter.reset - end - - # returns an integer \in (-\infty, 0] - # a number closer to 0 means the dependency is less constraining - # - # dependencies w/ 0 or 1 possibilities (ignoring version requirements) - # are given very negative values, so they _always_ sort first, - # before dependencies that are unconstrained - def amount_constrained(dependency) - @amount_constrained ||= {} - @amount_constrained[dependency.name] ||= if (base = @base[dependency.name]) && !base.empty? - dependency.requirement.satisfied_by?(base.first.version) ? 0 : 1 - else - all = index_for(dependency).search(dependency.name).size - - if all <= 1 - all - 1_000_000 - else - search = search_for(dependency) - search = prerelease_specified[dependency.name] ? search.count : search.count {|s| !s.version.prerelease? } - search - all - end - end end - def verify_gemfile_dependencies_are_found!(requirements) - requirements.map! do |requirement| - name = requirement.name - next requirement if name == "bundler" - next if requirement.gem_platforms(@platforms).empty? - next requirement unless search_for(requirement).empty? - next unless requirement.current_platform? + def prepare_dependencies(requirements, packages) + to_dependency_hash(requirements, packages).map do |dep_package, dep_constraint| + name = dep_package.name + next if dep_package.platforms.empty? + next [dep_package, dep_constraint] if name == "bundler" + next [dep_package, dep_constraint] unless versions_for(dep_package, dep_constraint.range).empty? + next unless dep_package.current_platform? - raise GemNotFound, gem_not_found_message(name, requirement, source_for(name)) - end.compact! + raise GemNotFound, gem_not_found_message(dep_package, dep_constraint) + end.compact.to_h end - def gem_not_found_message(name, requirement, source, extra_message = "") + def gem_not_found_message(package, requirement) + name = package.name + source = source_for(name) specs = source.specs.search(name).sort_by {|s| [s.version, s.platform.to_s] } matching_part = name - requirement_label = SharedHelpers.pretty_dependency(requirement) + requirement_label = SharedHelpers.pretty_dependency(package.dependency) cache_message = begin " or in gems cached in #{Bundler.settings.app_cache_path}" if Bundler.app_cache.exist? rescue GemfileNotFound nil end - specs_matching_requirement = specs.select {| spec| requirement.matches_spec?(spec) } + specs_matching_requirement = specs.select {| spec| requirement_satisfied_by?(package.dependency.requirement, spec) } if specs_matching_requirement.any? specs = specs_matching_requirement matching_part = requirement_label - platforms = requirement.gem_platforms(@platforms) + platforms = package.platforms platform_label = platforms.size == 1 ? "platform '#{platforms.first}" : "platforms '#{platforms.join("', '")}" requirement_label = "#{requirement_label}' with #{platform_label}" end - message = String.new("Could not find gem '#{requirement_label}'#{extra_message} in #{source}#{cache_message}.\n") + message = String.new("Could not find gem '#{requirement_label}' in #{source}#{cache_message}.\n") if specs.any? message << "\nThe source contains the following gems matching '#{matching_part}':\n" @@ -265,116 +295,62 @@ module Bundler message end - def version_conflict_message(e) - # only show essential conflicts, if possible - conflicts = e.conflicts.dup - - if conflicts["bundler"] - conflicts.replace("bundler" => conflicts["bundler"]) - else - conflicts.delete_if do |_name, conflict| - deps = conflict.requirement_trees.map(&:last).flatten(1) - !Bundler::VersionRanges.empty?(*Bundler::VersionRanges.for_many(deps.map(&:requirement))) + def requirement_to_range(requirement) + ranges = requirement.requirements.map do |(op, version)| + ver = Resolver::Candidate.new(version) + + case op + when "~>" + name = "~> #{ver}" + bump = Resolver::Candidate.new(version.bump.to_s + ".A") + PubGrub::VersionRange.new(:name => name, :min => ver, :max => bump, :include_min => true) + when ">" + PubGrub::VersionRange.new(:min => ver) + when ">=" + PubGrub::VersionRange.new(:min => ver, :include_min => true) + when "<" + PubGrub::VersionRange.new(:max => ver) + when "<=" + PubGrub::VersionRange.new(:max => ver, :include_max => true) + when "=" + PubGrub::VersionRange.new(:min => ver, :max => ver, :include_min => true, :include_max => true) + when "!=" + PubGrub::VersionRange.new(:min => ver, :max => ver, :include_min => true, :include_max => true).invert + else + raise "bad version specifier: #{op}" end end - e = Molinillo::VersionConflict.new(conflicts, e.specification_provider) unless conflicts.empty? - - e.message_with_trees( - :full_message_for_conflict => lambda do |name, conflict| - trees = conflict.requirement_trees - - # called first, because we want to reduce the amount of work required to find maximal empty sets - trees = trees.uniq {|t| t.flatten.map {|dep| [dep.name, dep.requirement] } } - - # bail out if tree size is too big for Array#combination to make any sense - if trees.size <= 15 - maximal = 1.upto(trees.size).map do |size| - trees.map(&:last).flatten(1).combination(size).to_a - end.flatten(1).select do |deps| - Bundler::VersionRanges.empty?(*Bundler::VersionRanges.for_many(deps.map(&:requirement))) - end.min_by(&:size) + ranges.inject(&:intersect) + end - trees.reject! {|t| !maximal.include?(t.last) } if maximal + def to_dependency_hash(dependencies, packages) + dependencies.inject({}) do |deps, dep| + package = packages[dep.name] - trees.sort_by! {|t| t.reverse.map(&:name) } - end + current_req = deps[package] + new_req = parse_dependency(package, dep.requirement) - if trees.size > 1 || name == "bundler" - o = if name.end_with?("\0") - String.new("Bundler found conflicting requirements for the #{name} version:") - else - String.new("Bundler could not find compatible versions for gem \"#{name}\":") - end - o << %(\n) - o << %( In #{name_for_explicit_dependency_source}:\n) - o << trees.map do |tree| - t = "".dup - depth = 2 - - base_tree = tree.first - base_tree_name = base_tree.name - - if base_tree_name.end_with?("\0") - t = nil - else - tree.each do |req| - t << " " * depth << SharedHelpers.pretty_dependency(req) - unless tree.last == req - if spec = conflict.activated_by_name[req.name] - t << %( was resolved to #{spec.version}, which) - end - t << %( depends on) - end - t << %(\n) - depth += 1 - end - end - t - end.compact.join("\n") - else - o = String.new - end + deps[package] = if current_req + current_req.intersect(new_req) + else + new_req + end - if name == "bundler" - o << %(\n Current Bundler version:\n bundler (#{Bundler::VERSION})) - - conflict_dependency = conflict.requirement - conflict_requirement = conflict_dependency.requirement - other_bundler_required = !conflict_requirement.satisfied_by?(Gem::Version.new(Bundler::VERSION)) - - if other_bundler_required - o << "\n\n" - - candidate_specs = source_for(:default_bundler).specs.search(conflict_dependency) - if candidate_specs.any? - target_version = candidate_specs.last.version - new_command = [File.basename($PROGRAM_NAME), "_#{target_version}_", *ARGV].join(" ") - o << "Your bundle requires a different version of Bundler than the one you're running.\n" - o << "Install the necessary version with `gem install bundler:#{target_version}` and rerun bundler using `#{new_command}`\n" - else - o << "Your bundle requires a different version of Bundler than the one you're running, and that version could not be found.\n" - end - end - elsif name.end_with?("\0") - o << %(\n Current #{name} version:\n #{SharedHelpers.pretty_dependency(@metadata_requirements.find {|req| req.name == name })}\n\n) - elsif !conflict.existing - o << "\n" - - relevant_source = conflict.requirement.source || source_for(name) - - extra_message = if trees.first.size > 1 - ", which is required by gem '#{SharedHelpers.pretty_dependency(trees.first[-2])}'," - else - "" - end - - o << gem_not_found_message(name, conflict.requirement, relevant_source, extra_message) - end + deps + end + end - o - end - ) + def bundler_not_found_message(conflict_dependency) + candidate_specs = source_for(:default_bundler).specs.search("bundler").select {|spec| requirement_satisfied_by?(conflict_dependency, spec) } + if candidate_specs.any? + target_version = candidate_specs.last.version + new_command = [File.basename($PROGRAM_NAME), "_#{target_version}_", *ARGV].join(" ") + "Your bundle requires a different version of Bundler than the one you're running.\n" \ + "Install the necessary version with `gem install bundler:#{target_version}` and rerun bundler using `#{new_command}`\n" + else + "Your bundle requires a different version of Bundler than the one you're running, and that version could not be found.\n" + end end end end -- cgit v1.2.1