diff options
75 files changed, 2710 insertions, 3152 deletions
diff --git a/lib/bundler.rb b/lib/bundler.rb index 1a94e0c963..b20179934a 100644 --- a/lib/bundler.rb +++ b/lib/bundler.rb @@ -75,7 +75,6 @@ module Bundler autoload :StubSpecification, File.expand_path("bundler/stub_specification", __dir__) autoload :UI, File.expand_path("bundler/ui", __dir__) autoload :URICredentialsFilter, File.expand_path("bundler/uri_credentials_filter", __dir__) - autoload :VersionRanges, File.expand_path("bundler/version_ranges", __dir__) class << self def configure diff --git a/lib/bundler/cli/check.rb b/lib/bundler/cli/check.rb index 65c51337d2..cc1f37f0c3 100644 --- a/lib/bundler/cli/check.rb +++ b/lib/bundler/cli/check.rb @@ -17,7 +17,7 @@ module Bundler begin definition.resolve_only_locally! not_installed = definition.missing_specs - rescue GemNotFound, VersionConflict + rescue GemNotFound, SolveFailure Bundler.ui.error "Bundler can't satisfy your Gemfile's dependencies." Bundler.ui.warn "Install missing gems with `bundle install`." exit 1 diff --git a/lib/bundler/cli/lock.rb b/lib/bundler/cli/lock.rb index 7d613a6644..cbd3f5a6fe 100644 --- a/lib/bundler/cli/lock.rb +++ b/lib/bundler/cli/lock.rb @@ -15,8 +15,8 @@ module Bundler end print = options[:print] - ui = Bundler.ui - Bundler.ui = UI::Silent.new if print + previous_ui_level = Bundler.ui.level + Bundler.ui.level = "silent" if print Bundler::Fetcher.disable_endpoint = options["full-index"] @@ -61,7 +61,7 @@ module Bundler definition.lock(file) end - Bundler.ui = ui + Bundler.ui.level = previous_ui_level end end end diff --git a/lib/bundler/definition.rb b/lib/bundler/definition.rb index 3836841f3f..9043efe408 100644 --- a/lib/bundler/definition.rb +++ b/lib/bundler/definition.rb @@ -150,7 +150,7 @@ module Bundler end def gem_version_promoter - @gem_version_promoter ||= GemVersionPromoter.new(@originally_locked_specs, @unlock[:gems]) + @gem_version_promoter ||= GemVersionPromoter.new end def resolve_only_locally! @@ -276,7 +276,7 @@ module Bundler end else Bundler.ui.debug("Found changes from the lockfile, re-resolving dependencies because #{change_reason}") - resolver.start(expanded_dependencies) + start_resolution end end @@ -299,7 +299,7 @@ module Bundler if @locked_bundler_version locked_major = @locked_bundler_version.segments.first - current_major = Gem::Version.create(Bundler::VERSION).segments.first + current_major = Bundler.gem_version.segments.first updating_major = locked_major < current_major end @@ -474,7 +474,7 @@ module Bundler @resolver ||= begin last_resolve = converge_locked_specs remove_ruby_from_platforms_if_necessary!(current_dependencies) - Resolver.new(source_requirements, last_resolve, gem_version_promoter, additional_base_requirements_for_resolve(last_resolve), platforms) + Resolver.new(source_requirements, last_resolve, gem_version_promoter, additional_base_requirements_for_resolve(last_resolve)) end end @@ -482,6 +482,23 @@ module Bundler @expanded_dependencies ||= dependencies + metadata_dependencies end + def resolution_packages + @resolution_packages ||= begin + packages = Hash.new do |h, k| + h[k] = Resolver::Package.new(k, @platforms, @originally_locked_specs, @unlock[:gems]) + end + + expanded_dependencies.each do |dep| + name = dep.name + platforms = dep.gem_platforms(@platforms) + + packages[name] = Resolver::Package.new(name, platforms, @originally_locked_specs, @unlock[:gems], :dependency => dep) + end + + packages + end + end + def filter_specs(specs, deps) SpecSet.new(specs).for(deps, false, platforms) end @@ -512,16 +529,22 @@ module Bundler break if incomplete_specs.empty? Bundler.ui.debug("The lockfile does not have all gems needed for the current platform though, Bundler will still re-resolve dependencies") - @resolve = resolver.start(expanded_dependencies, :exclude_specs => incomplete_specs) + @resolve = start_resolution(:exclude_specs => incomplete_specs) specs = resolve.materialize(dependencies) end - bundler = sources.metadata_source.specs.search(Gem::Dependency.new("bundler", VERSION)).last + bundler = sources.metadata_source.specs.search(["bundler", Bundler.gem_version]).last specs["bundler"] = bundler specs end + def start_resolution(exclude_specs: []) + result = resolver.start(expanded_dependencies, resolution_packages, :exclude_specs => exclude_specs) + + SpecSet.new(SpecSet.new(result).for(dependencies, false, @platforms)) + end + def precompute_source_requirements_for_indirect_dependencies? @remote && sources.non_global_rubygems_sources.all?(&:dependency_api_available?) && !sources.aggregate_global_source? end diff --git a/lib/bundler/dependency.rb b/lib/bundler/dependency.rb index 605000ba53..695e5c12b2 100644 --- a/lib/bundler/dependency.rb +++ b/lib/bundler/dependency.rb @@ -50,6 +50,7 @@ module Bundler # Returns the platforms this dependency is valid for, in the same order as # passed in the `valid_platforms` parameter def gem_platforms(valid_platforms) + return [Gem::Platform::RUBY] if @force_ruby_platform return valid_platforms if @platforms.empty? valid_platforms.select {|p| expanded_platforms.include?(GemHelpers.generic(p)) } diff --git a/lib/bundler/errors.rb b/lib/bundler/errors.rb index 15069065ff..5839fc6a73 100644 --- a/lib/bundler/errors.rb +++ b/lib/bundler/errors.rb @@ -21,16 +21,7 @@ module Bundler class InstallError < BundlerError; status_code(5); end # Internal error, should be rescued - class VersionConflict < BundlerError - attr_reader :conflicts - - def initialize(conflicts, msg = nil) - super(msg) - @conflicts = conflicts - end - - status_code(6) - end + class SolveFailure < BundlerError; status_code(6); end class GemNotFound < BundlerError; status_code(7); end class InstallHookError < BundlerError; status_code(8); end diff --git a/lib/bundler/gem_version_promoter.rb b/lib/bundler/gem_version_promoter.rb index ee2c38a6ec..d6ae65998f 100644 --- a/lib/bundler/gem_version_promoter.rb +++ b/lib/bundler/gem_version_promoter.rb @@ -7,9 +7,7 @@ module Bundler # available dependency versions as found in its index, before returning it to # to the resolution engine to select the best version. class GemVersionPromoter - DEBUG = ENV["BUNDLER_DEBUG_RESOLVER"] || ENV["DEBUG_RESOLVER"] - - attr_reader :level, :locked_specs, :unlock_gems + attr_reader :level # By default, strict is false, meaning every available version of a gem # is returned from sort_versions. The order gives preference to the @@ -24,24 +22,12 @@ module Bundler # existing in the referenced source. attr_accessor :strict - attr_accessor :prerelease_specified - - # Given a list of locked_specs and a list of gems to unlock creates a - # GemVersionPromoter instance. + # Creates a GemVersionPromoter instance. # - # @param locked_specs [SpecSet] All current locked specs. Unlike Definition - # where this list is empty if all gems are being updated, this should - # always be populated for all gems so this class can properly function. - # @param unlock_gems [String] List of gem names being unlocked. If empty, - # all gems will be considered unlocked. # @return [GemVersionPromoter] - def initialize(locked_specs = SpecSet.new([]), unlock_gems = []) + def initialize @level = :major @strict = false - @locked_specs = locked_specs - @unlock_gems = unlock_gems - @sort_versions = {} - @prerelease_specified = {} end # @param value [Symbol] One of three Symbols: :major, :minor or :patch. @@ -55,34 +41,19 @@ module Bundler @level = v end - # Given a Dependency and an Array of Specifications of available versions for a - # gem, this method will return the Array of Specifications sorted (and possibly - # truncated if strict is true) in an order to give preference to the current - # level (:major, :minor or :patch) when resolution is deciding what versions - # best resolve all dependencies in the bundle. - # @param dep [Dependency] The Dependency of the gem. - # @param spec_groups [Specification] An array of Specifications for the same gem - # named in the @dep param. + # Given a Resolver::Package and an Array of Specifications of available + # versions for a gem, this method will return the Array of Specifications + # sorted (and possibly truncated if strict is true) in an order to give + # preference to the current level (:major, :minor or :patch) when resolution + # is deciding what versions best resolve all dependencies in the bundle. + # @param package [Resolver::Package] The package being resolved. + # @param specs [Specification] An array of Specifications for the package. # @return [Specification] A new instance of the Specification Array sorted and # possibly filtered. - def sort_versions(dep, spec_groups) - @sort_versions[dep] ||= begin - gem_name = dep.name + def sort_versions(package, specs) + specs = filter_dep_specs(specs, package) if strict - # An Array per version returned, different entries for different platforms. - # We only need the version here so it's ok to hard code this to the first instance. - locked_spec = locked_specs[gem_name].first - - if strict - filter_dep_specs(spec_groups, locked_spec) - else - sort_dep_specs(spec_groups, locked_spec) - end - end - end - - def reset - @sort_versions = {} + sort_dep_specs(specs, package) end # @return [bool] Convenience method for testing value of level variable. @@ -97,11 +68,13 @@ module Bundler private - def filter_dep_specs(spec_groups, locked_spec) - res = spec_groups.select do |spec_group| - if locked_spec && !major? - gsv = spec_group.version - lsv = locked_spec.version + def filter_dep_specs(specs, package) + locked_version = package.locked_version + + specs.select do |spec| + if locked_version && !major? + gsv = spec.version + lsv = locked_version must_match = minor? ? [0] : [0, 1] @@ -111,63 +84,53 @@ module Bundler true end end - - sort_dep_specs(res, locked_spec) end - def sort_dep_specs(spec_groups, locked_spec) - @locked_version = locked_spec&.version - @gem_name = locked_spec&.name + def sort_dep_specs(specs, package) + locked_version = package.locked_version - result = spec_groups.sort do |a, b| - @a_ver = a.version - @b_ver = b.version - - unless @gem_name && @prerelease_specified[@gem_name] - a_pre = @a_ver.prerelease? - b_pre = @b_ver.prerelease? + result = specs.sort do |a, b| + unless locked_version && package.prerelease_specified? + a_pre = a.prerelease? + b_pre = b.prerelease? next -1 if a_pre && !b_pre next 1 if b_pre && !a_pre end if major? - @a_ver <=> @b_ver - elsif either_version_older_than_locked - @a_ver <=> @b_ver - elsif segments_do_not_match(:major) - @b_ver <=> @a_ver - elsif !minor? && segments_do_not_match(:minor) - @b_ver <=> @a_ver + a <=> b + elsif either_version_older_than_locked(a, b, locked_version) + a <=> b + elsif segments_do_not_match(a, b, :major) + b <=> a + elsif !minor? && segments_do_not_match(a, b, :minor) + b <=> a else - @a_ver <=> @b_ver + a <=> b end end - post_sort(result) + post_sort(result, package.unlock?, locked_version) end - def either_version_older_than_locked - @locked_version && (@a_ver < @locked_version || @b_ver < @locked_version) + def either_version_older_than_locked(a, b, locked_version) + locked_version && (a.version < locked_version || b.version < locked_version) end - def segments_do_not_match(level) + def segments_do_not_match(a, b, level) index = [:major, :minor].index(level) - @a_ver.segments[index] != @b_ver.segments[index] - end - - def unlocking_gem? - unlock_gems.empty? || (@gem_name && unlock_gems.include?(@gem_name)) + a.segments[index] != b.segments[index] end # Specific version moves can't always reliably be done during sorting # as not all elements are compared against each other. - def post_sort(result) + def post_sort(result, unlock, locked_version) # default :major behavior in Bundler does not do this return result if major? - if unlocking_gem? || @locked_version.nil? + if unlock || locked_version.nil? result else - move_version_to_end(result, @locked_version) + move_version_to_end(result, locked_version) end end diff --git a/lib/bundler/index.rb b/lib/bundler/index.rb index ed16c90a3a..0301986ca9 100644 --- a/lib/bundler/index.rb +++ b/lib/bundler/index.rb @@ -70,7 +70,7 @@ module Bundler case query when Gem::Specification, RemoteSpecification, LazySpecification, EndpointSpecification then search_by_spec(query) when String then specs_by_name(query) - when Gem::Dependency then search_by_dependency(query) + when Array then specs_by_name_and_version(*query) else raise "You can't search for a #{query.inspect}." end @@ -157,20 +157,12 @@ module Bundler private - def specs_by_name(name) - @specs[name].values + def specs_by_name_and_version(name, version) + specs_by_name(name).select {|spec| spec.version == version } end - def search_by_dependency(dependency) - @cache[dependency] ||= begin - specs = specs_by_name(dependency.name) - found = specs.select do |spec| - next true if spec.source.is_a?(Source::Gemspec) - dependency.matches_spec?(spec) - end - - found - end + def specs_by_name(name) + @specs[name].values end EMPTY_SEARCH = [].freeze diff --git a/lib/bundler/inline.rb b/lib/bundler/inline.rb index 25e055fbe4..6664d3ebc4 100644 --- a/lib/bundler/inline.rb +++ b/lib/bundler/inline.rb @@ -34,7 +34,8 @@ def gemfile(install = false, options = {}, &gemfile) opts = options.dup ui = opts.delete(:ui) { Bundler::UI::Shell.new } - ui.level = "silent" if opts.delete(:quiet) + ui.level = "silent" if opts.delete(:quiet) || !install + Bundler.ui = ui raise ArgumentError, "Unknown options: #{opts.keys.join(", ")}" unless opts.empty? begin @@ -52,7 +53,6 @@ def gemfile(install = false, options = {}, &gemfile) def definition.lock(*); end definition.validate_runtime! - Bundler.ui = install ? ui : Bundler::UI::Silent.new if install || definition.missing_specs? Bundler.settings.temporary(:inline => true, :no_install => false) do installer = Bundler::Installer.install(Bundler.root, definition, :system => true) diff --git a/lib/bundler/lazy_specification.rb b/lib/bundler/lazy_specification.rb index 949e8264ba..21a6f96f69 100644 --- a/lib/bundler/lazy_specification.rb +++ b/lib/bundler/lazy_specification.rb @@ -79,7 +79,7 @@ module Bundler candidates = if source.is_a?(Source::Path) || !ruby_platform_materializes_to_ruby_platform? target_platform = ruby_platform_materializes_to_ruby_platform? ? platform : local_platform - GemHelpers.select_best_platform_match(source.specs.search(Dependency.new(name, version)), target_platform) + GemHelpers.select_best_platform_match(source.specs.search([name, version]), target_platform) else source.specs.search(self) end 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 diff --git a/lib/bundler/resolver/base.rb b/lib/bundler/resolver/base.rb index a8f42dc994..78b798f4ec 100644 --- a/lib/bundler/resolver/base.rb +++ b/lib/bundler/resolver/base.rb @@ -20,15 +20,11 @@ module Bundler @base_requirements ||= build_base_requirements end - def unlock_deps(deps) - exact, lower_bound = deps.partition(&:specific?) + def unlock_names(names) + names.each do |name| + @base.delete_by_name(name) - exact.each do |exact_dep| - @base.delete_by_name_and_version(exact_dep.name, exact_dep.requirement.requirements.first.last) - end - - lower_bound.each do |lower_bound_dep| - @additional_base_requirements.delete(lower_bound_dep) + @additional_base_requirements.reject! {|dep| dep.name == name } end @base_requirements = nil @@ -39,10 +35,10 @@ module Bundler def build_base_requirements base_requirements = {} @base.each do |ls| - dep = Dependency.new(ls.name, ls.version) - base_requirements[ls.name] = dep + req = Gem::Requirement.new(ls.version) + base_requirements[ls.name] = req end - @additional_base_requirements.each {|d| base_requirements[d.name] = d } + @additional_base_requirements.each {|d| base_requirements[d.name] = d.requirement } base_requirements end end diff --git a/lib/bundler/resolver/candidate.rb b/lib/bundler/resolver/candidate.rb new file mode 100644 index 0000000000..cf5691ccc7 --- /dev/null +++ b/lib/bundler/resolver/candidate.rb @@ -0,0 +1,92 @@ +# frozen_string_literal: true + +require_relative "spec_group" + +module Bundler + class Resolver + # + # This class is a PubGrub compatible "Version" class that takes Bundler + # resolution complexities into account. + # + # Each Resolver::Candidate has a underlying `Gem::Version` plus a set of + # platforms. For example, 1.1.0-x86_64-linux is a different resolution candidate + # from 1.1.0 (generic). This is because different platform variants of the + # same gem version can bring different dependencies, so they need to be + # considered separately. + # + # Some candidates may also keep some information explicitly about the + # package the refer to. These candidates are referred to as "canonical" and + # are used when materializing resolution results back into RubyGems + # specifications that can be installed, written to lock files, and so on. + # + class Candidate + include Comparable + + attr_reader :version + + def initialize(version, specs: []) + @spec_group = Resolver::SpecGroup.new(specs) + @platforms = specs.map(&:platform).sort_by(&:to_s).uniq + @version = Gem::Version.new(version) + @ruby_only = @platforms == [Gem::Platform::RUBY] + end + + def dependencies + @spec_group.dependencies + end + + def to_specs(package) + return [] if package.meta? + + @spec_group.to_specs(package.force_ruby_platform?) + end + + def prerelease? + @version.prerelease? + end + + def segments + @version.segments + end + + def sort_obj + [@version, @ruby_only ? -1 : 1] + end + + def canonical? + !@spec_group.empty? + end + + def <=>(other) + return unless other.is_a?(self.class) + return @version <=> other.version unless canonical? && other.canonical? + + sort_obj <=> other.sort_obj + end + + def ==(other) + return unless other.is_a?(self.class) + return @version == other.version unless canonical? && other.canonical? + + sort_obj == other.sort_obj + end + + def eql?(other) + return unless other.is_a?(self.class) + return @version.eql?(other.version) unless canonical? || other.canonical? + + sort_obj.eql?(other.sort_obj) + end + + def hash + sort_obj.hash + end + + def to_s + return @version.to_s if @platforms.empty? || @ruby_only + + "#{@version} (#{@platforms.join(", ")})" + end + end + end +end diff --git a/lib/bundler/resolver/package.rb b/lib/bundler/resolver/package.rb new file mode 100644 index 0000000000..fa283baca8 --- /dev/null +++ b/lib/bundler/resolver/package.rb @@ -0,0 +1,67 @@ +# frozen_string_literal: true + +module Bundler + class Resolver + # + # Represents a gem being resolved, in a format PubGrub likes. + # + # The class holds the following information: + # + # * Platforms this gem will be resolved on. + # * The locked version of this gem resolution should favor (if any). + # * Whether the gem should be unlocked to its latest version. + # * The dependency explicit set in the Gemfile for this gem (if any). + # + class Package + attr_reader :name, :platforms, :dependency + + def initialize(name, platforms, locked_specs, unlock, dependency: nil) + @name = name + @platforms = platforms + @locked_specs = locked_specs + @unlock = unlock + @dependency = dependency + end + + def to_s + @name.delete("\0") + end + + def root? + false + end + + def meta? + @name.end_with?("\0") + end + + def ==(other) + self.class == other.class && @name == other.name + end + + def hash + @name.hash + end + + def locked_version + @locked_specs[name].first&.version + end + + def unlock? + @unlock.empty? || @unlock.include?(name) + end + + def prerelease_specified? + @dependency&.prerelease? + end + + def force_ruby_platform? + @dependency&.force_ruby_platform + end + + def current_platform? + @dependency&.current_platform? + end + end + end +end diff --git a/lib/bundler/resolver/root.rb b/lib/bundler/resolver/root.rb new file mode 100644 index 0000000000..e5eb634fb8 --- /dev/null +++ b/lib/bundler/resolver/root.rb @@ -0,0 +1,25 @@ +# frozen_string_literal: true + +require_relative "package" + +module Bundler + class Resolver + # + # Represents the Gemfile from the resolver's perspective. It's the root + # package and Gemfile entries depend on it. + # + class Root < Package + def initialize(name) + @name = name + end + + def meta? + true + end + + def root? + true + end + end + end +end diff --git a/lib/bundler/resolver/spec_group.rb b/lib/bundler/resolver/spec_group.rb index ac32c3c119..b44c19a73f 100644 --- a/lib/bundler/resolver/spec_group.rb +++ b/lib/bundler/resolver/spec_group.rb @@ -3,20 +3,27 @@ module Bundler class Resolver class SpecGroup - attr_accessor :name, :version, :source - attr_accessor :activated_platforms, :force_ruby_platform + def initialize(specs) + @specs = specs + end - def initialize(specs, relevant_platforms) - @exemplary_spec = specs.first - @name = @exemplary_spec.name - @version = @exemplary_spec.version - @source = @exemplary_spec.source + def empty? + @specs.empty? + end - @activated_platforms = relevant_platforms - @specs = specs + def name + @name ||= exemplary_spec.name + end + + def version + @version ||= exemplary_spec.version + end + + def source + @source ||= exemplary_spec.source end - def to_specs + def to_specs(force_ruby_platform) @specs.map do |s| lazy_spec = LazySpecification.new(name, version, s.platform, source) lazy_spec.force_ruby_platform = force_ruby_platform @@ -26,44 +33,27 @@ module Bundler end def to_s - activated_platforms_string = sorted_activated_platforms.join(", ") - "#{name} (#{version}) (#{activated_platforms_string})" + sorted_spec_names.join(", ") end - def dependencies_for_activated_platforms - @dependencies_for_activated_platforms ||= @specs.map do |spec| + def dependencies + @dependencies ||= @specs.map do |spec| __dependencies(spec) + metadata_dependencies(spec) end.flatten.uniq end - def ==(other) - return unless other.is_a?(SpecGroup) - name == other.name && - version == other.version && - sorted_activated_platforms == other.sorted_activated_platforms && - source == other.source - end - - def eql?(other) - return unless other.is_a?(SpecGroup) - name.eql?(other.name) && - version.eql?(other.version) && - sorted_activated_platforms.eql?(other.sorted_activated_platforms) && - source.eql?(other.source) - end - - def hash - name.hash ^ version.hash ^ sorted_activated_platforms.hash ^ source.hash - end - protected - def sorted_activated_platforms - activated_platforms.sort_by(&:to_s) + def sorted_spec_names + @sorted_spec_names ||= @specs.map(&:full_name).sort end private + def exemplary_spec + @specs.first + end + def __dependencies(spec) dependencies = [] spec.dependencies.each do |dep| diff --git a/lib/bundler/source/metadata.rb b/lib/bundler/source/metadata.rb index 23531b8bd4..593da6d1a7 100644 --- a/lib/bundler/source/metadata.rb +++ b/lib/bundler/source/metadata.rb @@ -15,7 +15,6 @@ module Bundler s.version = VERSION s.license = "MIT" s.platform = Gem::Platform::RUBY - s.source = self s.authors = ["bundler team"] s.bindir = "exe" s.homepage = "https://bundler.io" diff --git a/lib/bundler/spec_set.rb b/lib/bundler/spec_set.rb index 21d57fdab4..a3d9218593 100644 --- a/lib/bundler/spec_set.rb +++ b/lib/bundler/spec_set.rb @@ -122,8 +122,8 @@ module Bundler @specs.detect {|spec| spec.name == name && spec.match_platform(platform) } end - def delete_by_name_and_version(name, version) - @specs.reject! {|spec| spec.name == name && spec.version == version } + def delete_by_name(name) + @specs.reject! {|spec| spec.name == name } @lookup = nil @sorted = nil end @@ -165,7 +165,7 @@ module Bundler cgems = extract_circular_gems(error) raise CyclicDependencyError, "Your bundle requires gems that depend" \ " on each other, creating an infinite loop. Please remove either" \ - " gem '#{cgems[1]}' or gem '#{cgems[0]}' and try again." + " gem '#{cgems[0]}' or gem '#{cgems[1]}' and try again." end end diff --git a/lib/bundler/ui/shell.rb b/lib/bundler/ui/shell.rb index 384752a340..4139585c47 100644 --- a/lib/bundler/ui/shell.rb +++ b/lib/bundler/ui/shell.rb @@ -20,29 +20,52 @@ module Bundler @shell.set_color(string, *color) end - def info(msg, newline = nil) - tell_me(msg, nil, newline) if level("info") + def info(msg = nil, newline = nil) + return unless info? + + tell_me(msg || yield, nil, newline) end - def confirm(msg, newline = nil) - tell_me(msg, :green, newline) if level("confirm") + def confirm(msg = nil, newline = nil) + return unless confirm? + + tell_me(msg || yield, :green, newline) end - def warn(msg, newline = nil, color = :yellow) - return unless level("warn") + def warn(msg = nil, newline = nil, color = :yellow) + return unless warn? return if @warning_history.include? msg @warning_history << msg - tell_err(msg, color, newline) + tell_err(msg || yield, color, newline) + end + + def error(msg = nil, newline = nil, color = :red) + return unless error? + + tell_err(msg || yield, color, newline) + end + + def debug(msg = nil, newline = nil) + return unless debug? + + tell_me(msg || yield, nil, newline) + end + + def info? + level("info") + end + + def confirm? + level("confirm") end - def error(msg, newline = nil, color = :red) - return unless level("error") - tell_err(msg, color, newline) + def warn? + level("warn") end - def debug(msg, newline = nil) - tell_me(msg, nil, newline) if debug? + def error? + level("error") end def debug? diff --git a/lib/bundler/ui/silent.rb b/lib/bundler/ui/silent.rb index dca1b2ac86..fa3292bdc9 100644 --- a/lib/bundler/ui/silent.rb +++ b/lib/bundler/ui/silent.rb @@ -13,30 +13,46 @@ module Bundler string end - def info(message, newline = nil) + def info(message = nil, newline = nil) end - def confirm(message, newline = nil) + def confirm(message = nil, newline = nil) end - def warn(message, newline = nil) + def warn(message = nil, newline = nil) @warnings |= [message] end - def error(message, newline = nil) + def error(message = nil, newline = nil) end - def debug(message, newline = nil) + def debug(message = nil, newline = nil) + end + + def confirm? + false + end + + def error? + false end def debug? false end + def info? + false + end + def quiet? false end + def warn? + false + end + def ask(message) end diff --git a/lib/bundler/vendor/molinillo/lib/molinillo.rb b/lib/bundler/vendor/molinillo/lib/molinillo.rb deleted file mode 100644 index a52b96deaf..0000000000 --- a/lib/bundler/vendor/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' - -# Bundler::Molinillo is a generic dependency resolution algorithm. -module Bundler::Molinillo -end diff --git a/lib/bundler/vendor/molinillo/lib/molinillo/delegates/resolution_state.rb b/lib/bundler/vendor/molinillo/lib/molinillo/delegates/resolution_state.rb deleted file mode 100644 index bcacf35243..0000000000 --- a/lib/bundler/vendor/molinillo/lib/molinillo/delegates/resolution_state.rb +++ /dev/null @@ -1,57 +0,0 @@ -# frozen_string_literal: true - -module Bundler::Molinillo - # @!visibility private - module Delegates - # Delegates all {Bundler::Molinillo::ResolutionState} methods to a `#state` property. - module ResolutionState - # (see Bundler::Molinillo::ResolutionState#name) - def name - current_state = state || Bundler::Molinillo::ResolutionState.empty - current_state.name - end - - # (see Bundler::Molinillo::ResolutionState#requirements) - def requirements - current_state = state || Bundler::Molinillo::ResolutionState.empty - current_state.requirements - end - - # (see Bundler::Molinillo::ResolutionState#activated) - def activated - current_state = state || Bundler::Molinillo::ResolutionState.empty - current_state.activated - end - - # (see Bundler::Molinillo::ResolutionState#requirement) - def requirement - current_state = state || Bundler::Molinillo::ResolutionState.empty - current_state.requirement - end - - # (see Bundler::Molinillo::ResolutionState#possibilities) - def possibilities - current_state = state || Bundler::Molinillo::ResolutionState.empty - current_state.possibilities - end - - # (see Bundler::Molinillo::ResolutionState#depth) - def depth - current_state = state || Bundler::Molinillo::ResolutionState.empty - current_state.depth - end - - # (see Bundler::Molinillo::ResolutionState#conflicts) - def conflicts - current_state = state || Bundler::Molinillo::ResolutionState.empty - current_state.conflicts - end - - # (see Bundler::Molinillo::ResolutionState#unused_unwind_options) - def unused_unwind_options - current_state = state || Bundler::Molinillo::ResolutionState.empty - current_state.unused_unwind_options - end - end - end -end diff --git a/lib/bundler/vendor/molinillo/lib/molinillo/delegates/specification_provider.rb b/lib/bundler/vendor/molinillo/lib/molinillo/delegates/specification_provider.rb deleted file mode 100644 index f8c695c1ed..0000000000 --- a/lib/bundler/vendor/molinillo/lib/molinillo/delegates/specification_provider.rb +++ /dev/null @@ -1,88 +0,0 @@ -# frozen_string_literal: true - -module Bundler::Molinillo - module Delegates - # Delegates all {Bundler::Molinillo::SpecificationProvider} methods to a - # `#specification_provider` property. - module SpecificationProvider - # (see Bundler::Molinillo::SpecificationProvider#search_for) - def search_for(dependency) - with_no_such_dependency_error_handling do - specification_provider.search_for(dependency) - end - end - - # (see Bundler::Molinillo::SpecificationProvider#dependencies_for) - def dependencies_for(specification) - with_no_such_dependency_error_handling do - specification_provider.dependencies_for(specification) - end - end - - # (see Bundler::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 Bundler::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 Bundler::Molinillo::SpecificationProvider#name_for) - def name_for(dependency) - with_no_such_dependency_error_handling do - specification_provider.name_for(dependency) - end - end - - # (see Bundler::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 Bundler::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 Bundler::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 Bundler::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/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb b/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb deleted file mode 100644 index 4d577213b9..0000000000 --- a/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb +++ /dev/null @@ -1,255 +0,0 @@ -# frozen_string_literal: true - -require_relative '../../../../vendored_tsort' - -require_relative 'dependency_graph/log' -require_relative 'dependency_graph/vertex' - -module Bundler::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 Bundler::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) - Bundler::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/bundler/vendor/molinillo/lib/molinillo/dependency_graph/action.rb b/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/action.rb deleted file mode 100644 index c04c7eec9c..0000000000 --- a/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/action.rb +++ /dev/null @@ -1,36 +0,0 @@ -# frozen_string_literal: true - -module Bundler::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/bundler/vendor/molinillo/lib/molinillo/dependency_graph/add_edge_no_circular.rb b/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/add_edge_no_circular.rb deleted file mode 100644 index 946a08236e..0000000000 --- a/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/add_edge_no_circular.rb +++ /dev/null @@ -1,66 +0,0 @@ -# frozen_string_literal: true - -require_relative 'action' -module Bundler::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/bundler/vendor/molinillo/lib/molinillo/dependency_graph/add_vertex.rb b/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/add_vertex.rb deleted file mode 100644 index 483527daf8..0000000000 --- a/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/add_vertex.rb +++ /dev/null @@ -1,62 +0,0 @@ -# frozen_string_literal: true - -require_relative 'action' -module Bundler::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/bundler/vendor/molinillo/lib/molinillo/dependency_graph/delete_edge.rb b/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/delete_edge.rb deleted file mode 100644 index d81940585a..0000000000 --- a/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/delete_edge.rb +++ /dev/null @@ -1,63 +0,0 @@ -# frozen_string_literal: true - -require_relative 'action' -module Bundler::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/bundler/vendor/molinillo/lib/molinillo/dependency_graph/detach_vertex_named.rb b/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/detach_vertex_named.rb deleted file mode 100644 index 36fce7c526..0000000000 --- a/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/detach_vertex_named.rb +++ /dev/null @@ -1,61 +0,0 @@ -# frozen_string_literal: true - -require_relative 'action' -module Bundler::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/bundler/vendor/molinillo/lib/molinillo/dependency_graph/log.rb b/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/log.rb deleted file mode 100644 index 6f0de19886..0000000000 --- a/lib/bundler/vendor/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 Bundler::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/bundler/vendor/molinillo/lib/molinillo/dependency_graph/set_payload.rb b/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/set_payload.rb deleted file mode 100644 index 2e9b90e6cd..0000000000 --- a/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/set_payload.rb +++ /dev/null @@ -1,46 +0,0 @@ -# frozen_string_literal: true - -require_relative 'action' -module Bundler::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/bundler/vendor/molinillo/lib/molinillo/dependency_graph/tag.rb b/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/tag.rb deleted file mode 100644 index 5b5da3e4f9..0000000000 --- a/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/tag.rb +++ /dev/null @@ -1,36 +0,0 @@ -# frozen_string_literal: true - -require_relative 'action' -module Bundler::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/bundler/vendor/molinillo/lib/molinillo/dependency_graph/vertex.rb b/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/vertex.rb deleted file mode 100644 index 1185a8ab05..0000000000 --- a/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/vertex.rb +++ /dev/null @@ -1,164 +0,0 @@ -# frozen_string_literal: true - -module Bundler::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/bundler/vendor/molinillo/lib/molinillo/errors.rb b/lib/bundler/vendor/molinillo/lib/molinillo/errors.rb deleted file mode 100644 index 8c8cafb447..0000000000 --- a/lib/bundler/vendor/molinillo/lib/molinillo/errors.rb +++ /dev/null @@ -1,149 +0,0 @@ -# frozen_string_literal: true - -module Bundler::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 - - full_message_for_conflict = opts.delete(:full_message_for_conflict) do - proc do |name, conflict| - o = "\n".dup << 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 - end - - conflicts.sort.reduce(''.dup) do |o, (name, conflict)| - o << full_message_for_conflict.call(name, conflict) - end.strip - end - end -end diff --git a/lib/bundler/vendor/molinillo/lib/molinillo/gem_metadata.rb b/lib/bundler/vendor/molinillo/lib/molinillo/gem_metadata.rb deleted file mode 100644 index a0cfc21672..0000000000 --- a/lib/bundler/vendor/molinillo/lib/molinillo/gem_metadata.rb +++ /dev/null @@ -1,6 +0,0 @@ -# frozen_string_literal: true - -module Bundler::Molinillo - # The version of Bundler::Molinillo. - VERSION = '0.8.0'.freeze -end diff --git a/lib/bundler/vendor/molinillo/lib/molinillo/modules/specification_provider.rb b/lib/bundler/vendor/molinillo/lib/molinillo/modules/specification_provider.rb deleted file mode 100644 index eeae79af3c..0000000000 --- a/lib/bundler/vendor/molinillo/lib/molinillo/modules/specification_provider.rb +++ /dev/null @@ -1,112 +0,0 @@ -# frozen_string_literal: true - -module Bundler::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 Bundler::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/bundler/vendor/molinillo/lib/molinillo/modules/ui.rb b/lib/bundler/vendor/molinillo/lib/molinillo/modules/ui.rb deleted file mode 100644 index a166bc6991..0000000000 --- a/lib/bundler/vendor/molinillo/lib/molinillo/modules/ui.rb +++ /dev/null @@ -1,67 +0,0 @@ -# frozen_string_literal: true - -module Bundler::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/bundler/vendor/molinillo/lib/molinillo/resolution.rb b/lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb deleted file mode 100644 index c689ca7635..0000000000 --- a/lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb +++ /dev/null @@ -1,839 +0,0 @@ -# frozen_string_literal: true - -module Bundler::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 Bundler::Molinillo::Delegates::ResolutionState - include Bundler::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/bundler/vendor/molinillo/lib/molinillo/resolver.rb b/lib/bundler/vendor/molinillo/lib/molinillo/resolver.rb deleted file mode 100644 index 95eaab5991..0000000000 --- a/lib/bundler/vendor/molinillo/lib/molinillo/resolver.rb +++ /dev/null @@ -1,46 +0,0 @@ -# frozen_string_literal: true - -require_relative 'dependency_graph' - -module Bundler::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/bundler/vendor/molinillo/lib/molinillo/state.rb b/lib/bundler/vendor/molinillo/lib/molinillo/state.rb deleted file mode 100644 index 68fa1f54e3..0000000000 --- a/lib/bundler/vendor/molinillo/lib/molinillo/state.rb +++ /dev/null @@ -1,58 +0,0 @@ -# frozen_string_literal: true - -module Bundler::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/bundler/vendor/pub_grub/LICENSE.txt b/lib/bundler/vendor/pub_grub/LICENSE.txt new file mode 100644 index 0000000000..411840a4a0 --- /dev/null +++ b/lib/bundler/vendor/pub_grub/LICENSE.txt @@ -0,0 +1,21 @@ +The MIT License (MIT) + +Copyright (c) 2018 John Hawthorn + +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/bundler/vendor/pub_grub/lib/pub_grub.rb b/lib/bundler/vendor/pub_grub/lib/pub_grub.rb new file mode 100644 index 0000000000..eaaba3fc98 --- /dev/null +++ b/lib/bundler/vendor/pub_grub/lib/pub_grub.rb @@ -0,0 +1,31 @@ +require_relative "pub_grub/package" +require_relative "pub_grub/static_package_source" +require_relative "pub_grub/term" +require_relative "pub_grub/version_range" +require_relative "pub_grub/version_constraint" +require_relative "pub_grub/version_union" +require_relative "pub_grub/version_solver" +require_relative "pub_grub/incompatibility" +require_relative 'pub_grub/solve_failure' +require_relative 'pub_grub/failure_writer' +require_relative 'pub_grub/version' + +module Bundler::PubGrub + class << self + attr_writer :logger + + def logger + @logger || default_logger + end + + private + + def default_logger + require "logger" + + logger = ::Logger.new(STDERR) + logger.level = $DEBUG ? ::Logger::DEBUG : ::Logger::WARN + @logger = logger + end + end +end diff --git a/lib/bundler/vendor/pub_grub/lib/pub_grub/assignment.rb b/lib/bundler/vendor/pub_grub/lib/pub_grub/assignment.rb new file mode 100644 index 0000000000..2236a97b5b --- /dev/null +++ b/lib/bundler/vendor/pub_grub/lib/pub_grub/assignment.rb @@ -0,0 +1,20 @@ +module Bundler::PubGrub + class Assignment + attr_reader :term, :cause, :decision_level, :index + def initialize(term, cause, decision_level, index) + @term = term + @cause = cause + @decision_level = decision_level + @index = index + end + + def self.decision(package, version, decision_level, index) + term = Term.new(VersionConstraint.exact(package, version), true) + new(term, :decision, decision_level, index) + end + + def decision? + cause == :decision + end + end +end diff --git a/lib/bundler/vendor/pub_grub/lib/pub_grub/basic_package_source.rb b/lib/bundler/vendor/pub_grub/lib/pub_grub/basic_package_source.rb new file mode 100644 index 0000000000..dce20d37ad --- /dev/null +++ b/lib/bundler/vendor/pub_grub/lib/pub_grub/basic_package_source.rb @@ -0,0 +1,189 @@ +require_relative 'version_constraint' +require_relative 'incompatibility' + +module Bundler::PubGrub + # Types: + # + # Where possible, Bundler::PubGrub will accept user-defined types, so long as they quack. + # + # ## "Package": + # + # This class will be used to represent the various packages being solved for. + # .to_s will be called when displaying errors and debugging info, it should + # probably return the package's name. + # It must also have a reasonable definition of #== and #hash + # + # Example classes: String ("rails") + # + # + # ## "Version": + # + # This class will be used to represent a single version number. + # + # Versions don't need to store their associated package, however they will + # only be compared against other versions of the same package. + # + # It must be Comparible (and implement <=> reasonably) + # + # Example classes: Gem::Version, Integer + # + # + # ## "Dependency" + # + # This class represents the requirement one package has on another. It is + # returned by dependencies_for(package, version) and will be passed to + # parse_dependency to convert it to a format Bundler::PubGrub understands. + # + # It must also have a reasonable definition of #== + # + # Example classes: String ("~> 1.0"), Gem::Requirement + # + class BasicPackageSource + # Override me! + # + # This is called per package to find all possible versions of a package. + # + # It is called at most once per-package + # + # Returns: Array of versions for a package, in preferred order of selection + def all_versions_for(package) + raise NotImplementedError + end + + # Override me! + # + # Returns: Hash in the form of { package => requirement, ... } + def dependencies_for(package, version) + raise NotImplementedError + end + + # Override me! + # + # Convert a (user-defined) dependency into a format Bundler::PubGrub understands. + # + # Package is passed to this method but for many implementations is not + # needed. + # + # Returns: either a Bundler::PubGrub::VersionRange, Bundler::PubGrub::VersionUnion, or a + # Bundler::PubGrub::VersionConstraint + def parse_dependency(package, dependency) + raise NotImplementedError + end + + # Override me! + # + # If not overridden, this will call dependencies_for with the root package. + # + # Returns: Hash in the form of { package => requirement, ... } (see dependencies_for) + def root_dependencies + dependencies_for(@root_package, @root_version) + end + + # Override me (maybe) + # + # If not overridden, the order returned by all_versions_for will be used + # + # Returns: Array of versions in preferred order + def sort_versions_by_preferred(package, sorted_versions) + indexes = @version_indexes[package] + sorted_versions.sort_by { |version| indexes[version] } + end + + def initialize + @root_package = Package.root + @root_version = Package.root_version + + @cached_versions = Hash.new do |h,k| + if k == @root_package + h[k] = [@root_version] + else + h[k] = all_versions_for(k) + end + end + @sorted_versions = Hash.new { |h,k| h[k] = @cached_versions[k].sort } + @version_indexes = Hash.new { |h,k| h[k] = @cached_versions[k].each.with_index.to_h } + + @cached_dependencies = Hash.new do |packages, package| + if package == @root_package + packages[package] = { + @root_version => root_dependencies + } + else + packages[package] = Hash.new do |versions, version| + versions[version] = dependencies_for(package, version) + end + end + end + end + + def versions_for(package, range=VersionRange.any) + versions = range.select_versions(@sorted_versions[package]) + + # Conditional avoids (among other things) calling + # sort_versions_by_preferred with the root package + if versions.size > 1 + sort_versions_by_preferred(package, versions) + else + versions + end + end + + def no_versions_incompatibility_for(_package, unsatisfied_term) + cause = Incompatibility::NoVersions.new(unsatisfied_term) + + Incompatibility.new([unsatisfied_term], cause: cause) + 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_name| + low = high = sorted_versions.index(version) + + # find version low such that all >= low share the same dep + while low > 0 && + package_deps[sorted_versions[low - 1]][dep_package] == dep_constraint_name + low -= 1 + end + low = + if low == 0 + nil + else + sorted_versions[low] + end + + # 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_name + high += 1 + end + high = + if high == sorted_versions.length + nil + else + sorted_versions[high] + end + + range = VersionRange.new(min: low, max: high, include_min: true) + + self_constraint = VersionConstraint.new(package, range: range) + + if !@packages.include?(dep_package) + # no such package -> this version is invalid + end + + dep_constraint = parse_dependency(dep_package, dep_constraint_name) + if !dep_constraint + # falsey indicates this dependency was invalid + cause = Bundler::PubGrub::Incompatibility::InvalidDependency.new(dep_package, dep_constraint_name) + return [Incompatibility.new([Term.new(self_constraint, true)], cause: cause)] + elsif !dep_constraint.is_a?(VersionConstraint) + # Upgrade range/union to VersionConstraint + dep_constraint = VersionConstraint.new(dep_package, range: dep_constraint) + end + + Incompatibility.new([Term.new(self_constraint, true), Term.new(dep_constraint, false)], cause: :dependency) + end + end + end +end diff --git a/lib/bundler/vendor/pub_grub/lib/pub_grub/failure_writer.rb b/lib/bundler/vendor/pub_grub/lib/pub_grub/failure_writer.rb new file mode 100644 index 0000000000..ee099b23f4 --- /dev/null +++ b/lib/bundler/vendor/pub_grub/lib/pub_grub/failure_writer.rb @@ -0,0 +1,182 @@ +module Bundler::PubGrub + class FailureWriter + def initialize(root) + @root = root + + # { Incompatibility => Integer } + @derivations = {} + + # [ [ String, Integer or nil ] ] + @lines = [] + + # { Incompatibility => Integer } + @line_numbers = {} + + count_derivations(root) + end + + def write + return @root.to_s unless @root.conflict? + + visit(@root) + + padding = @line_numbers.empty? ? 0 : "(#{@line_numbers.values.last}) ".length + + @lines.map do |message, number| + next "" if message.empty? + + lead = number ? "(#{number}) " : "" + lead = lead.ljust(padding) + message = message.gsub("\n", "\n" + " " * (padding + 2)) + "#{lead}#{message}" + end.join("\n") + end + + private + + def write_line(incompatibility, message, numbered:) + if numbered + number = @line_numbers.length + 1 + @line_numbers[incompatibility] = number + end + + @lines << [message, number] + end + + def visit(incompatibility, conclusion: false) + raise unless incompatibility.conflict? + + numbered = conclusion || @derivations[incompatibility] > 1; + conjunction = conclusion || incompatibility == @root ? "So," : "And" + + cause = incompatibility.cause + + if cause.conflict.conflict? && cause.other.conflict? + conflict_line = @line_numbers[cause.conflict] + other_line = @line_numbers[cause.other] + + if conflict_line && other_line + write_line( + incompatibility, + "Because #{cause.conflict} (#{conflict_line})\nand #{cause.other} (#{other_line}),\n#{incompatibility}.", + numbered: numbered + ) + elsif conflict_line || other_line + with_line = conflict_line ? cause.conflict : cause.other + without_line = conflict_line ? cause.other : cause.conflict + line = @line_numbers[with_line] + + visit(without_line); + write_line( + incompatibility, + "#{conjunction} because #{with_line} (#{line}),\n#{incompatibility}.", + numbered: numbered + ) + else + single_line_conflict = single_line?(cause.conflict.cause) + single_line_other = single_line?(cause.other.cause) + + if single_line_conflict || single_line_other + first = single_line_other ? cause.conflict : cause.other + second = single_line_other ? cause.other : cause.conflict + visit(first) + visit(second) + write_line( + incompatibility, + "Thus, #{incompatibility}.", + numbered: numbered + ) + else + visit(cause.conflict, conclusion: true) + @lines << ["", nil] + visit(cause.other) + + write_line( + incompatibility, + "#{conjunction} because #{cause.conflict} (#{@line_numbers[cause.conflict]}),\n#{incompatibility}.", + numbered: numbered + ) + end + end + elsif cause.conflict.conflict? || cause.other.conflict? + derived = cause.conflict.conflict? ? cause.conflict : cause.other + ext = cause.conflict.conflict? ? cause.other : cause.conflict + + derived_line = @line_numbers[derived] + if derived_line + write_line( + incompatibility, + "Because #{ext}\nand #{derived} (#{derived_line}),\n#{incompatibility}.", + numbered: numbered + ) + elsif collapsible?(derived) + derived_cause = derived.cause + if derived_cause.conflict.conflict? + collapsed_derived = derived_cause.conflict + collapsed_ext = derived_cause.other + else + collapsed_derived = derived_cause.other + collapsed_ext = derived_cause.conflict + end + + visit(collapsed_derived) + + write_line( + incompatibility, + "#{conjunction} because #{collapsed_ext}\nand #{ext},\n#{incompatibility}.", + numbered: numbered + ) + else + visit(derived) + write_line( + incompatibility, + "#{conjunction} because #{ext},\n#{incompatibility}.", + numbered: numbered + ) + end + else + write_line( + incompatibility, + "Because #{cause.conflict}\nand #{cause.other},\n#{incompatibility}.", + numbered: numbered + ) + end + end + + def single_line?(cause) + !cause.conflict.conflict? && !cause.other.conflict? + end + + def collapsible?(incompatibility) + return false if @derivations[incompatibility] > 1 + + cause = incompatibility.cause + # If incompatibility is derived from two derived incompatibilities, + # there are too many transitive causes to display concisely. + return false if cause.conflict.conflict? && cause.other.conflict? + + # If incompatibility is derived from two external incompatibilities, it + # tends to be confusing to collapse it. + return false unless cause.conflict.conflict? || cause.other.conflict? + + # If incompatibility's internal cause is numbered, collapsing it would + # get too noisy. + complex = cause.conflict.conflict? ? cause.conflict : cause.other + + !@line_numbers.has_key?(complex) + end + + def count_derivations(incompatibility) + if @derivations.has_key?(incompatibility) + @derivations[incompatibility] += 1 + else + @derivations[incompatibility] = 1 + if incompatibility.conflict? + cause = incompatibility.cause + count_derivations(cause.conflict) + count_derivations(cause.other) + end + end + end + end +end diff --git a/lib/bundler/vendor/pub_grub/lib/pub_grub/incompatibility.rb b/lib/bundler/vendor/pub_grub/lib/pub_grub/incompatibility.rb new file mode 100644 index 0000000000..51e1fc3cdd --- /dev/null +++ b/lib/bundler/vendor/pub_grub/lib/pub_grub/incompatibility.rb @@ -0,0 +1,146 @@ +module Bundler::PubGrub + class Incompatibility + ConflictCause = Struct.new(:incompatibility, :satisfier) do + alias_method :conflict, :incompatibility + alias_method :other, :satisfier + end + + InvalidDependency = Struct.new(:package, :constraint) do + end + + NoVersions = Struct.new(:constraint) do + end + + attr_reader :terms, :cause + + def initialize(terms, cause:, custom_explanation: nil) + @cause = cause + @terms = cleanup_terms(terms) + @custom_explanation = custom_explanation + + if cause == :dependency && @terms.length != 2 + raise ArgumentError, "a dependency Incompatibility must have exactly two terms. Got #{@terms.inspect}" + end + end + + def hash + cause.hash ^ terms.hash + end + + def eql?(other) + cause.eql?(other.cause) && + terms.eql?(other.terms) + end + + def failure? + terms.empty? || (terms.length == 1 && Package.root?(terms[0].package) && terms[0].positive?) + end + + def conflict? + ConflictCause === cause + end + + # Returns all external incompatibilities in this incompatibility's + # derivation graph + def external_incompatibilities + if conflict? + [ + cause.conflict, + cause.other + ].flat_map(&:external_incompatibilities) + else + [this] + end + end + + def to_s + return @custom_explanation if @custom_explanation + + case cause + when :root + "(root dependency)" + when :dependency + "#{terms[0].to_s(allow_every: true)} depends on #{terms[1].invert}" + when Bundler::PubGrub::Incompatibility::InvalidDependency + "#{terms[0].to_s(allow_every: true)} depends on unknown package #{cause.package}" + when Bundler::PubGrub::Incompatibility::NoVersions + "no versions satisfy #{cause.constraint}" + when Bundler::PubGrub::Incompatibility::ConflictCause + if failure? + "version solving has failed" + elsif terms.length == 1 + term = terms[0] + if term.positive? + "#{terms[0].to_s(allow_every: true)} is forbidden" + else + "#{terms[0].invert} is required" + end + else + if terms.all?(&:positive?) + if terms.length == 2 + "#{terms[0].to_s(allow_every: true)} is incompatible with #{terms[1]}" + else + "one of #{terms.map(&:to_s).join(" or ")} must be false" + end + elsif terms.all?(&:negative?) + if terms.length == 2 + "either #{terms[0].invert} or #{terms[1].invert}" + else + "one of #{terms.map(&:invert).join(" or ")} must be true"; + end + else + positive = terms.select(&:positive?) + negative = terms.select(&:negative?).map(&:invert) + + if positive.length == 1 + "#{positive[0].to_s(allow_every: true)} requires #{negative.join(" or ")}" + else + "if #{positive.join(" and ")} then #{negative.join(" or ")}" + end + end + end + else + raise "unhandled cause: #{cause.inspect}" + end + end + + def inspect + "#<#{self.class} #{to_s}>" + end + + def pretty_print(q) + q.group 2, "#<#{self.class}", ">" do + q.breakable + q.text to_s + + q.breakable + q.text " caused by " + q.pp @cause + end + end + + private + + def cleanup_terms(terms) + terms.each do |term| + raise "#{term.inspect} must be a term" unless term.is_a?(Term) + end + + if terms.length != 1 && ConflictCause === cause + terms = terms.reject do |term| + term.positive? && Package.root?(term.package) + end + end + + # Optimized simple cases + return terms if terms.length <= 1 + return terms if terms.length == 2 && terms[0].package != terms[1].package + + terms.group_by(&:package).map do |package, common_terms| + common_terms.inject do |acc, term| + acc.intersect(term) + end + end + end + end +end diff --git a/lib/bundler/vendor/pub_grub/lib/pub_grub/package.rb b/lib/bundler/vendor/pub_grub/lib/pub_grub/package.rb new file mode 100644 index 0000000000..efb9d3da16 --- /dev/null +++ b/lib/bundler/vendor/pub_grub/lib/pub_grub/package.rb @@ -0,0 +1,43 @@ +# frozen_string_literal: true + +module Bundler::PubGrub + class Package + + attr_reader :name + + def initialize(name) + @name = name + end + + def inspect + "#<#{self.class} #{name.inspect}>" + end + + def <=>(other) + name <=> other.name + end + + ROOT = Package.new(:root) + ROOT_VERSION = 0 + + def self.root + ROOT + end + + def self.root_version + ROOT_VERSION + end + + def self.root?(package) + if package.respond_to?(:root?) + package.root? + else + package == root + end + end + + def to_s + name.to_s + end + end +end diff --git a/lib/bundler/vendor/pub_grub/lib/pub_grub/partial_solution.rb b/lib/bundler/vendor/pub_grub/lib/pub_grub/partial_solution.rb new file mode 100644 index 0000000000..4c4b8ca844 --- /dev/null +++ b/lib/bundler/vendor/pub_grub/lib/pub_grub/partial_solution.rb @@ -0,0 +1,121 @@ +require_relative 'assignment' + +module Bundler::PubGrub + class PartialSolution + attr_reader :assignments, :decisions + attr_reader :attempted_solutions + + def initialize + reset! + + @attempted_solutions = 1 + @backtracking = false + end + + def decision_level + @decisions.length + end + + def relation(term) + package = term.package + return :overlap if !@terms.key?(package) + + @relation_cache[package][term] ||= + @terms[package].relation(term) + end + + def satisfies?(term) + relation(term) == :subset + end + + def derive(term, cause) + add_assignment(Assignment.new(term, cause, decision_level, assignments.length)) + end + + def satisfier(term) + assignment = + @assignments_by[term.package].bsearch do |assignment_by| + @cumulative_assignments[assignment_by].satisfies?(term) + end + + assignment || raise("#{term} unsatisfied") + end + + # A list of unsatisfied terms + def unsatisfied + @required.keys.reject do |package| + @decisions.key?(package) + end.map do |package| + @terms[package] + end + end + + def decide(package, version) + @attempted_solutions += 1 if @backtracking + @backtracking = false; + + decisions[package] = version + assignment = Assignment.decision(package, version, decision_level, assignments.length) + add_assignment(assignment) + end + + def backtrack(previous_level) + @backtracking = true + + new_assignments = assignments.select do |assignment| + assignment.decision_level <= previous_level + end + + new_decisions = Hash[decisions.first(previous_level)] + + reset! + + @decisions = new_decisions + + new_assignments.each do |assignment| + add_assignment(assignment) + end + end + + private + + def reset! + # { Array<Assignment> } + @assignments = [] + + # { Package => Array<Assignment> } + @assignments_by = Hash.new { |h,k| h[k] = [] } + @cumulative_assignments = {}.compare_by_identity + + # { Package => Package::Version } + @decisions = {} + + # { Package => Term } + @terms = {} + @relation_cache = Hash.new { |h,k| h[k] = {} } + + # { Package => Boolean } + @required = {} + end + + def add_assignment(assignment) + term = assignment.term + package = term.package + + @assignments << assignment + @assignments_by[package] << assignment + + @required[package] = true if term.positive? + + if @terms.key?(package) + old_term = @terms[package] + @terms[package] = old_term.intersect(term) + else + @terms[package] = term + end + @relation_cache[package].clear + + @cumulative_assignments[assignment] = @terms[package] + end + end +end diff --git a/lib/bundler/vendor/pub_grub/lib/pub_grub/rubygems.rb b/lib/bundler/vendor/pub_grub/lib/pub_grub/rubygems.rb new file mode 100644 index 0000000000..245c23be22 --- /dev/null +++ b/lib/bundler/vendor/pub_grub/lib/pub_grub/rubygems.rb @@ -0,0 +1,45 @@ +module Bundler::PubGrub + module RubyGems + extend self + + def requirement_to_range(requirement) + ranges = requirement.requirements.map do |(op, ver)| + case op + when "~>" + name = "~> #{ver}" + bump = ver.class.new(ver.bump.to_s + ".A") + VersionRange.new(name: name, min: ver, max: bump, include_min: true) + when ">" + VersionRange.new(min: ver) + when ">=" + VersionRange.new(min: ver, include_min: true) + when "<" + VersionRange.new(max: ver) + when "<=" + VersionRange.new(max: ver, include_max: true) + when "=" + VersionRange.new(min: ver, max: ver, include_min: true, include_max: true) + when "!=" + VersionRange.new(min: ver, max: ver, include_min: true, include_max: true).invert + else + raise "bad version specifier: #{op}" + end + end + + ranges.inject(&:intersect) + end + + def requirement_to_constraint(package, requirement) + Bundler::PubGrub::VersionConstraint.new(package, range: requirement_to_range(requirement)) + end + + def parse_range(dep) + requirement_to_range(Gem::Requirement.new(dep)) + end + + def parse_constraint(package, dep) + range = parse_range(dep) + Bundler::PubGrub::VersionConstraint.new(package, range: range) + end + end +end diff --git a/lib/bundler/vendor/pub_grub/lib/pub_grub/solve_failure.rb b/lib/bundler/vendor/pub_grub/lib/pub_grub/solve_failure.rb new file mode 100644 index 0000000000..961a7a7c0c --- /dev/null +++ b/lib/bundler/vendor/pub_grub/lib/pub_grub/solve_failure.rb @@ -0,0 +1,19 @@ +require_relative 'failure_writer' + +module Bundler::PubGrub + class SolveFailure < StandardError + attr_reader :incompatibility + + def initialize(incompatibility) + @incompatibility = incompatibility + end + + def to_s + "Could not find compatible versions\n\n#{explanation}" + end + + def explanation + @explanation ||= FailureWriter.new(@incompatibility).write + end + end +end diff --git a/lib/bundler/vendor/pub_grub/lib/pub_grub/static_package_source.rb b/lib/bundler/vendor/pub_grub/lib/pub_grub/static_package_source.rb new file mode 100644 index 0000000000..e895812bed --- /dev/null +++ b/lib/bundler/vendor/pub_grub/lib/pub_grub/static_package_source.rb @@ -0,0 +1,53 @@ +require_relative 'package' +require_relative 'version_constraint' +require_relative 'incompatibility' +require_relative 'basic_package_source' + +module Bundler::PubGrub + class StaticPackageSource < BasicPackageSource + class DSL + def initialize(packages, root_deps) + @packages = packages + @root_deps = root_deps + end + + def root(deps:) + @root_deps.update(deps) + end + + def add(name, version, deps: {}) + version = Gem::Version.new(version) + @packages[name] ||= {} + raise ArgumentError, "#{name} #{version} declared twice" if @packages[name].key?(version) + @packages[name][version] = deps + end + end + + def initialize + @root_deps = {} + @packages = {} + + yield DSL.new(@packages, @root_deps) + + super() + end + + def all_versions_for(package) + @packages[package].keys + end + + def root_dependencies + @root_deps + end + + def dependencies_for(package, version) + @packages[package][version] + end + + def parse_dependency(package, dependency) + return false unless @packages.key?(package) + + Bundler::PubGrub::RubyGems.parse_constraint(package, dependency) + end + end +end diff --git a/lib/bundler/vendor/pub_grub/lib/pub_grub/term.rb b/lib/bundler/vendor/pub_grub/lib/pub_grub/term.rb new file mode 100644 index 0000000000..1d0f763378 --- /dev/null +++ b/lib/bundler/vendor/pub_grub/lib/pub_grub/term.rb @@ -0,0 +1,105 @@ +module Bundler::PubGrub + class Term + attr_reader :package, :constraint, :positive + + def initialize(constraint, positive) + @constraint = constraint + @package = @constraint.package + @positive = positive + end + + def to_s(allow_every: false) + if positive + @constraint.to_s(allow_every: allow_every) + else + "not #{@constraint}" + end + end + + def hash + constraint.hash ^ positive.hash + end + + def eql?(other) + positive == other.positive && + constraint.eql?(other.constraint) + end + + def invert + self.class.new(@constraint, !@positive) + end + alias_method :inverse, :invert + + def intersect(other) + raise ArgumentError, "packages must match" if package != other.package + + if positive? && other.positive? + self.class.new(constraint.intersect(other.constraint), true) + elsif negative? && other.negative? + self.class.new(constraint.union(other.constraint), false) + else + positive = positive? ? self : other + negative = negative? ? self : other + self.class.new(positive.constraint.intersect(negative.constraint.invert), true) + end + end + + def difference(other) + intersect(other.invert) + end + + def relation(other) + if positive? && other.positive? + constraint.relation(other.constraint) + elsif negative? && other.positive? + if constraint.allows_all?(other.constraint) + :disjoint + else + :overlap + end + elsif positive? && other.negative? + if !other.constraint.allows_any?(constraint) + :subset + elsif other.constraint.allows_all?(constraint) + :disjoint + else + :overlap + end + elsif negative? && other.negative? + if constraint.allows_all?(other.constraint) + :subset + else + :overlap + end + else + raise + end + end + + def normalized_constraint + @normalized_constraint ||= positive ? constraint : constraint.invert + end + + def satisfies?(other) + raise ArgumentError, "packages must match" unless package == other.package + + relation(other) == :subset + end + + def positive? + @positive + end + + def negative? + !positive? + end + + def empty? + @empty ||= normalized_constraint.empty? + end + + def inspect + "#<#{self.class} #{self}>" + end + end +end diff --git a/lib/bundler/vendor/pub_grub/lib/pub_grub/version.rb b/lib/bundler/vendor/pub_grub/lib/pub_grub/version.rb new file mode 100644 index 0000000000..d7984b3863 --- /dev/null +++ b/lib/bundler/vendor/pub_grub/lib/pub_grub/version.rb @@ -0,0 +1,3 @@ +module Bundler::PubGrub + VERSION = "0.5.0" +end diff --git a/lib/bundler/vendor/pub_grub/lib/pub_grub/version_constraint.rb b/lib/bundler/vendor/pub_grub/lib/pub_grub/version_constraint.rb new file mode 100644 index 0000000000..c222542435 --- /dev/null +++ b/lib/bundler/vendor/pub_grub/lib/pub_grub/version_constraint.rb @@ -0,0 +1,124 @@ +require_relative 'version_range' + +module Bundler::PubGrub + class VersionConstraint + attr_reader :package, :range + + # @param package [Bundler::PubGrub::Package] + # @param range [Bundler::PubGrub::VersionRange] + def initialize(package, range: nil) + @package = package + @range = range + end + + def hash + package.hash ^ range.hash + end + + def eql?(other) + package.eql?(other.package) && + range.eql?(other.range) + end + + class << self + def exact(package, version) + range = VersionRange.new(min: version, max: version, include_min: true, include_max: true) + new(package, range: range) + end + + def any(package) + new(package, range: VersionRange.any) + end + + def empty(package) + new(package, range: VersionRange.empty) + end + end + + def intersect(other) + unless package == other.package + raise ArgumentError, "Can only intersect between VersionConstraint of the same package" + end + + self.class.new(package, range: range.intersect(other.range)) + end + + def union(other) + unless package == other.package + raise ArgumentError, "Can only intersect between VersionConstraint of the same package" + end + + self.class.new(package, range: range.union(other.range)) + end + + def invert + new_range = range.invert + self.class.new(package, range: new_range) + end + + def difference(other) + intersect(other.invert) + end + + def allows_all?(other) + range.allows_all?(other.range) + end + + def allows_any?(other) + range.intersects?(other.range) + end + + def subset?(other) + other.allows_all?(self) + end + + def overlap?(other) + other.allows_any?(self) + end + + def disjoint?(other) + !overlap?(other) + end + + def relation(other) + if subset?(other) + :subset + elsif overlap?(other) + :overlap + else + :disjoint + end + end + + def to_s(allow_every: false) + if Package.root?(package) + package.to_s + elsif allow_every && any? + "every version of #{package}" + else + "#{package} #{constraint_string}" + end + end + + def constraint_string + if any? + ">= 0" + else + range.to_s + end + end + + def empty? + range.empty? + end + + # Does this match every version of the package + def any? + range.any? + end + + def inspect + "#<#{self.class} #{self}>" + end + end +end diff --git a/lib/bundler/vendor/pub_grub/lib/pub_grub/version_range.rb b/lib/bundler/vendor/pub_grub/lib/pub_grub/version_range.rb new file mode 100644 index 0000000000..e384178973 --- /dev/null +++ b/lib/bundler/vendor/pub_grub/lib/pub_grub/version_range.rb @@ -0,0 +1,409 @@ +# frozen_string_literal: true + +module Bundler::PubGrub + class VersionRange + attr_reader :min, :max, :include_min, :include_max + + alias_method :include_min?, :include_min + alias_method :include_max?, :include_max + + class Empty < VersionRange + undef_method :min, :max + undef_method :include_min, :include_min? + undef_method :include_max, :include_max? + + def initialize + end + + def empty? + true + end + + def eql? + other.empty? + end + + def hash + [].hash + end + + def intersects?(_) + false + end + + def intersect(other) + self + end + + def allows_all?(other) + other.empty? + end + + def include?(_) + false + end + + def any? + false + end + + def to_s + "(no versions)" + end + + def ==(other) + other.class == self.class + end + + def invert + VersionRange.any + end + + def select_versions(_) + [] + end + end + + EMPTY = Empty.new + + def self.empty + EMPTY + end + + def self.any + new + end + + def initialize(min: nil, max: nil, include_min: false, include_max: false, name: nil) + @min = min + @max = max + @include_min = include_min + @include_max = include_max + @name = name + end + + def hash + @hash ||= min.hash ^ max.hash ^ include_min.hash ^ include_max.hash + end + + def eql?(other) + if other.is_a?(VersionRange) + min.eql?(other.min) && + max.eql?(other.max) && + include_min.eql?(other.include_min) && + include_max.eql?(other.include_max) + else + ranges.eql?(other.ranges) + end + end + + def ranges + [self] + end + + def include?(version) + compare_version(version) == 0 + end + + # Partitions passed versions into [lower, within, higher] + # + # versions must be sorted + def partition_versions(versions) + min_index = + if !min || versions.empty? + 0 + elsif include_min? + (0..versions.size).bsearch { |i| versions[i].nil? || versions[i] >= min } + else + (0..versions.size).bsearch { |i| versions[i].nil? || versions[i] > min } + end + + lower = versions.slice(0, min_index) + versions = versions.slice(min_index, versions.size) + + max_index = + if !max || versions.empty? + versions.size + elsif include_max? + (0..versions.size).bsearch { |i| versions[i].nil? || versions[i] > max } + else + (0..versions.size).bsearch { |i| versions[i].nil? || versions[i] >= max } + end + + [ + lower, + versions.slice(0, max_index), + versions.slice(max_index, versions.size) + ] + end + + # Returns versions which are included by this range. + # + # versions must be sorted + def select_versions(versions) + return versions if any? + + partition_versions(versions)[1] + end + + def compare_version(version) + if min + case version <=> min + when -1 + return -1 + when 0 + return -1 if !include_min + when 1 + end + end + + if max + case version <=> max + when -1 + when 0 + return 1 if !include_max + when 1 + return 1 + end + end + + 0 + end + + def strictly_lower?(other) + return false if !max || !other.min + + case max <=> other.min + when 0 + !include_max || !other.include_min + when -1 + true + when 1 + false + end + end + + def strictly_higher?(other) + other.strictly_lower?(self) + end + + def intersects?(other) + return false if other.empty? + return other.intersects?(self) if other.is_a?(VersionUnion) + !strictly_lower?(other) && !strictly_higher?(other) + end + alias_method :allows_any?, :intersects? + + def intersect(other) + return other if other.empty? + return other.intersect(self) if other.is_a?(VersionUnion) + + min_range = + if !min + other + elsif !other.min + self + else + case min <=> other.min + when 0 + include_min ? other : self + when -1 + other + when 1 + self + end + end + + max_range = + if !max + other + elsif !other.max + self + else + case max <=> other.max + when 0 + include_max ? other : self + when -1 + self + when 1 + other + end + end + + if !min_range.equal?(max_range) && min_range.min && max_range.max + case min_range.min <=> max_range.max + when -1 + when 0 + if !min_range.include_min || !max_range.include_max + return EMPTY + end + when 1 + return EMPTY + end + end + + VersionRange.new( + min: min_range.min, + include_min: min_range.include_min, + max: max_range.max, + include_max: max_range.include_max + ) + end + + # The span covered by two ranges + # + # If self and other are contiguous, this builds a union of the two ranges. + # (if they aren't you are probably calling the wrong method) + def span(other) + return self if other.empty? + + min_range = + if !min + self + elsif !other.min + other + else + case min <=> other.min + when 0 + include_min ? self : other + when -1 + self + when 1 + other + end + end + + max_range = + if !max + self + elsif !other.max + other + else + case max <=> other.max + when 0 + include_max ? self : other + when -1 + other + when 1 + self + end + end + + VersionRange.new( + min: min_range.min, + include_min: min_range.include_min, + max: max_range.max, + include_max: max_range.include_max + ) + end + + def union(other) + return other.union(self) if other.is_a?(VersionUnion) + + if contiguous_to?(other) + span(other) + else + VersionUnion.union([self, other]) + end + end + + def contiguous_to?(other) + return false if other.empty? + + intersects?(other) || + (min == other.max && (include_min || other.include_max)) || + (max == other.min && (include_max || other.include_min)) + end + + def allows_all?(other) + return true if other.empty? + + if other.is_a?(VersionUnion) + return VersionUnion.new([self]).allows_all?(other) + end + + return false if max && !other.max + return false if min && !other.min + + if min + case min <=> other.min + when -1 + when 0 + return false if !include_min && other.include_min + when 1 + return false + end + end + + if max + case max <=> other.max + when -1 + return false + when 0 + return false if !include_max && other.include_max + when 1 + end + end + + true + end + + def any? + !min && !max + end + + def empty? + false + end + + def to_s + @name ||= constraints.join(", ") + end + + def inspect + "#<#{self.class} #{to_s}>" + end + + def upper_invert + return self.class.empty unless max + + VersionRange.new(min: max, include_min: !include_max) + end + + def invert + return self.class.empty if any? + + low = VersionRange.new(max: min, include_max: !include_min) + high = VersionRange.new(min: max, include_min: !include_max) + + if !min + high + elsif !max + low + else + low.union(high) + end + end + + def ==(other) + self.class == other.class && + min == other.min && + max == other.max && + include_min == other.include_min && + include_max == other.include_max + end + + private + + def constraints + return ["any"] if any? + return ["= #{min}"] if min == max + + c = [] + c << "#{include_min ? ">=" : ">"} #{min}" if min + c << "#{include_max ? "<=" : "<"} #{max}" if max + c + end + + end +end diff --git a/lib/bundler/vendor/pub_grub/lib/pub_grub/version_solver.rb b/lib/bundler/vendor/pub_grub/lib/pub_grub/version_solver.rb new file mode 100644 index 0000000000..ea5e455968 --- /dev/null +++ b/lib/bundler/vendor/pub_grub/lib/pub_grub/version_solver.rb @@ -0,0 +1,240 @@ +require_relative 'partial_solution' +require_relative 'term' +require_relative 'incompatibility' +require_relative 'solve_failure' + +module Bundler::PubGrub + class VersionSolver + attr_reader :logger + attr_reader :source + attr_reader :solution + + def initialize(source:, root: Package.root, logger: Bundler::PubGrub.logger) + @logger = logger + + @source = source + + # { package => [incompatibility, ...]} + @incompatibilities = Hash.new do |h, k| + h[k] = [] + end + + @seen_incompatibilities = {} + + @solution = PartialSolution.new + + add_incompatibility Incompatibility.new([ + Term.new(VersionConstraint.any(root), false) + ], cause: :root) + + propagate(root) + end + + def solved? + solution.unsatisfied.empty? + end + + # Returns true if there is more work to be done, false otherwise + def work + return false if solved? + + next_package = choose_package_version + propagate(next_package) + + if solved? + logger.info { "Solution found after #{solution.attempted_solutions} attempts:" } + solution.decisions.each do |package, version| + next if Package.root?(package) + logger.info { "* #{package} #{version}" } + end + + false + else + true + end + end + + def solve + work until solved? + + solution.decisions + end + + alias_method :result, :solve + + private + + def propagate(initial_package) + changed = [initial_package] + while package = changed.shift + @incompatibilities[package].reverse_each do |incompatibility| + result = propagate_incompatibility(incompatibility) + if result == :conflict + root_cause = resolve_conflict(incompatibility) + changed.clear + changed << propagate_incompatibility(root_cause) + elsif result # should be a Package + changed << result + end + end + changed.uniq! + end + end + + def propagate_incompatibility(incompatibility) + unsatisfied = nil + incompatibility.terms.each do |term| + relation = solution.relation(term) + if relation == :disjoint + return nil + elsif relation == :overlap + # If more than one term is inconclusive, we can't deduce anything + return nil if unsatisfied + unsatisfied = term + end + end + + if !unsatisfied + return :conflict + end + + logger.debug { "derived: #{unsatisfied.invert}" } + + solution.derive(unsatisfied.invert, incompatibility) + + unsatisfied.package + end + + def next_package_to_try + solution.unsatisfied.min_by do |term| + package = term.package + range = term.constraint.range + 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.package + end + + def choose_package_version + if solution.unsatisfied.empty? + logger.info "No packages unsatisfied. Solving complete!" + return nil + end + + package = next_package_to_try + unsatisfied_term = solution.unsatisfied.find { |t| t.package == package } + version = source.versions_for(package, unsatisfied_term.constraint.range).first + + if version.nil? + add_incompatibility source.no_versions_incompatibility_for(package, unsatisfied_term) + return package + end + + conflict = false + + source.incompatibilities_for(package, version).each do |incompatibility| + if @seen_incompatibilities.include?(incompatibility) + logger.debug { "knew: #{incompatibility}" } + next + end + @seen_incompatibilities[incompatibility] = true + + add_incompatibility incompatibility + + conflict ||= incompatibility.terms.all? do |term| + term.package == package || solution.satisfies?(term) + end + end + + unless conflict + logger.info { "selecting #{package} #{version}" } + + solution.decide(package, version) + end + + package + end + + def resolve_conflict(incompatibility) + logger.info { "conflict: #{incompatibility}" } + + new_incompatibility = false + + while !incompatibility.failure? + most_recent_term = nil + most_recent_satisfier = nil + difference = nil + + previous_level = 1 + + incompatibility.terms.each do |term| + satisfier = solution.satisfier(term) + + if most_recent_satisfier.nil? + most_recent_term = term + most_recent_satisfier = satisfier + elsif most_recent_satisfier.index < satisfier.index + previous_level = [previous_level, most_recent_satisfier.decision_level].max + most_recent_term = term + most_recent_satisfier = satisfier + difference = nil + else + previous_level = [previous_level, satisfier.decision_level].max + end + + if most_recent_term == term + difference = most_recent_satisfier.term.difference(most_recent_term) + if difference.empty? + difference = nil + else + difference_satisfier = solution.satisfier(difference.inverse) + previous_level = [previous_level, difference_satisfier.decision_level].max + end + end + end + + if previous_level < most_recent_satisfier.decision_level || + most_recent_satisfier.decision? + + logger.info { "backtracking to #{previous_level}" } + solution.backtrack(previous_level) + + if new_incompatibility + add_incompatibility(incompatibility) + end + + return incompatibility + end + + new_terms = [] + new_terms += incompatibility.terms - [most_recent_term] + new_terms += most_recent_satisfier.cause.terms.reject { |term| + term.package == most_recent_satisfier.term.package + } + if difference + new_terms << difference.invert + end + + incompatibility = Incompatibility.new(new_terms, cause: Incompatibility::ConflictCause.new(incompatibility, most_recent_satisfier.cause)) + + new_incompatibility = true + + partially = difference ? " partially" : "" + logger.info { "! #{most_recent_term} is#{partially} satisfied by #{most_recent_satisfier.term}" } + logger.info { "! which is caused by #{most_recent_satisfier.cause}" } + logger.info { "! thus #{incompatibility}" } + end + + raise SolveFailure.new(incompatibility) + end + + def add_incompatibility(incompatibility) + logger.debug { "fact: #{incompatibility}" } + incompatibility.terms.each do |term| + package = term.package + @incompatibilities[package] << incompatibility + end + end + end +end diff --git a/lib/bundler/vendor/pub_grub/lib/pub_grub/version_union.rb b/lib/bundler/vendor/pub_grub/lib/pub_grub/version_union.rb new file mode 100644 index 0000000000..b66c603dfd --- /dev/null +++ b/lib/bundler/vendor/pub_grub/lib/pub_grub/version_union.rb @@ -0,0 +1,178 @@ +# frozen_string_literal: true + +module Bundler::PubGrub + class VersionUnion + attr_reader :ranges + + def self.normalize_ranges(ranges) + ranges = ranges.flat_map do |range| + range.ranges + end + + ranges.reject!(&:empty?) + + return [] if ranges.empty? + + mins, ranges = ranges.partition { |r| !r.min } + original_ranges = mins + ranges.sort_by { |r| [r.min, r.include_min ? 0 : 1] } + ranges = [original_ranges.shift] + original_ranges.each do |range| + if ranges.last.contiguous_to?(range) + ranges << ranges.pop.span(range) + else + ranges << range + end + end + + ranges + end + + def self.union(ranges, normalize: true) + ranges = normalize_ranges(ranges) if normalize + + if ranges.size == 0 + VersionRange.empty + elsif ranges.size == 1 + ranges[0] + else + new(ranges) + end + end + + def initialize(ranges) + raise ArgumentError unless ranges.all? { |r| r.instance_of?(VersionRange) } + @ranges = ranges + end + + def hash + ranges.hash + end + + def eql?(other) + ranges.eql?(other.ranges) + end + + def include?(version) + !!ranges.bsearch {|r| r.compare_version(version) } + end + + def select_versions(all_versions) + versions = [] + ranges.inject(all_versions) do |acc, range| + _, matching, higher = range.partition_versions(acc) + versions.concat matching + higher + end + versions + end + + def intersects?(other) + my_ranges = ranges.dup + other_ranges = other.ranges.dup + + my_range = my_ranges.shift + other_range = other_ranges.shift + while my_range && other_range + if my_range.intersects?(other_range) + return true + end + + if !my_range.max || (other_range.max && other_range.max < my_range.max) + other_range = other_ranges.shift + else + my_range = my_ranges.shift + end + end + end + alias_method :allows_any?, :intersects? + + def allows_all?(other) + my_ranges = ranges.dup + + my_range = my_ranges.shift + + other.ranges.all? do |other_range| + while my_range + break if my_range.allows_all?(other_range) + my_range = my_ranges.shift + end + + !!my_range + end + end + + def empty? + false + end + + def any? + false + end + + def intersect(other) + my_ranges = ranges.dup + other_ranges = other.ranges.dup + new_ranges = [] + + my_range = my_ranges.shift + other_range = other_ranges.shift + while my_range && other_range + new_ranges << my_range.intersect(other_range) + + if !my_range.max || (other_range.max && other_range.max < my_range.max) + other_range = other_ranges.shift + else + my_range = my_ranges.shift + end + end + new_ranges.reject!(&:empty?) + VersionUnion.union(new_ranges, normalize: false) + end + + def upper_invert + ranges.last.upper_invert + end + + def invert + ranges.map(&:invert).inject(:intersect) + end + + def union(other) + VersionUnion.union([self, other]) + end + + def to_s + output = [] + + ranges = self.ranges.dup + while !ranges.empty? + ne = [] + range = ranges.shift + while !ranges.empty? && ranges[0].min == range.max + ne << range.max + range = range.span(ranges.shift) + end + + ne.map! {|x| "!= #{x}" } + if ne.empty? + output << range.to_s + elsif range.any? + output << ne.join(', ') + else + output << "#{range}, #{ne.join(', ')}" + end + end + + output.join(" OR ") + end + + def inspect + "#<#{self.class} #{to_s}>" + end + + def ==(other) + self.class == other.class && + self.ranges == other.ranges + end + end +end diff --git a/lib/bundler/vendored_molinillo.rb b/lib/bundler/vendored_pub_grub.rb index d1976f5cb4..b36a996b29 100644 --- a/lib/bundler/vendored_molinillo.rb +++ b/lib/bundler/vendored_pub_grub.rb @@ -1,4 +1,4 @@ # frozen_string_literal: true module Bundler; end -require_relative "vendor/molinillo/lib/molinillo" +require_relative "vendor/pub_grub/lib/pub_grub" diff --git a/lib/bundler/version.rb b/lib/bundler/version.rb index 1acb00fd3a..a2a244c220 100644 --- a/lib/bundler/version.rb +++ b/lib/bundler/version.rb @@ -6,4 +6,8 @@ module Bundler def self.bundler_major_version @bundler_major_version ||= VERSION.split(".").first.to_i end + + def self.gem_version + @gem_version ||= Gem::Version.create(VERSION) + end end diff --git a/lib/bundler/version_ranges.rb b/lib/bundler/version_ranges.rb deleted file mode 100644 index 12a956d6a0..0000000000 --- a/lib/bundler/version_ranges.rb +++ /dev/null @@ -1,122 +0,0 @@ -# frozen_string_literal: true - -module Bundler - module VersionRanges - NEq = Struct.new(:version) - ReqR = Struct.new(:left, :right) - class ReqR - Endpoint = Struct.new(:version, :inclusive) do - def <=>(other) - if version.equal?(INFINITY) - return 0 if other.version.equal?(INFINITY) - return 1 - elsif other.version.equal?(INFINITY) - return -1 - end - - comp = version <=> other.version - return comp unless comp.zero? - - if inclusive && !other.inclusive - 1 - elsif !inclusive && other.inclusive - -1 - else - 0 - end - end - end - - def to_s - "#{left.inclusive ? "[" : "("}#{left.version}, #{right.version}#{right.inclusive ? "]" : ")"}" - end - INFINITY = begin - inf = Object.new - def inf.to_s - "∞" - end - def inf.<=>(other) - return 0 if other.equal?(self) - 1 - end - inf.freeze - end - ZERO = Gem::Version.new("0.a") - - def cover?(v) - return false if left.inclusive && left.version > v - return false if !left.inclusive && left.version >= v - - if right.version != INFINITY - return false if right.inclusive && right.version < v - return false if !right.inclusive && right.version <= v - end - - true - end - - def empty? - left.version == right.version && !(left.inclusive && right.inclusive) - end - - def single? - left.version == right.version - end - - def <=>(other) - return -1 if other.equal?(INFINITY) - - comp = left <=> other.left - return comp unless comp.zero? - - right <=> other.right - end - - UNIVERSAL = ReqR.new(ReqR::Endpoint.new(Gem::Version.new("0.a"), true), ReqR::Endpoint.new(ReqR::INFINITY, false)).freeze - end - - def self.for_many(requirements) - requirements = requirements.map(&:requirements).flatten(1).map {|r| r.join(" ") } - requirements << ">= 0.a" if requirements.empty? - requirement = Gem::Requirement.new(requirements) - self.for(requirement) - end - - def self.for(requirement) - ranges = requirement.requirements.map do |op, v| - case op - when "=" then ReqR.new(ReqR::Endpoint.new(v, true), ReqR::Endpoint.new(v, true)) - when "!=" then NEq.new(v) - when ">=" then ReqR.new(ReqR::Endpoint.new(v, true), ReqR::Endpoint.new(ReqR::INFINITY, false)) - when ">" then ReqR.new(ReqR::Endpoint.new(v, false), ReqR::Endpoint.new(ReqR::INFINITY, false)) - when "<" then ReqR.new(ReqR::Endpoint.new(ReqR::ZERO, true), ReqR::Endpoint.new(v, false)) - when "<=" then ReqR.new(ReqR::Endpoint.new(ReqR::ZERO, true), ReqR::Endpoint.new(v, true)) - when "~>" then ReqR.new(ReqR::Endpoint.new(v, true), ReqR::Endpoint.new(v.bump, false)) - else raise "unknown version op #{op} in requirement #{requirement}" - end - end.uniq - ranges, neqs = ranges.partition {|r| !r.is_a?(NEq) } - - [ranges.sort, neqs.map(&:version)] - end - - def self.empty?(ranges, neqs) - !ranges.reduce(ReqR::UNIVERSAL) do |last_range, curr_range| - next false unless last_range - next false if curr_range.single? && neqs.include?(curr_range.left.version) - next curr_range if last_range.right.version == ReqR::INFINITY - case last_range.right.version <=> curr_range.left.version - # higher - when 1 then next ReqR.new(curr_range.left, last_range.right) - # equal - when 0 - if last_range.right.inclusive && curr_range.left.inclusive && !neqs.include?(curr_range.left.version) - ReqR.new(curr_range.left, [curr_range.right, last_range.right].max) - end - # lower - when -1 then next false - end - end - end - end -end diff --git a/spec/bundler/bundler/definition_spec.rb b/spec/bundler/bundler/definition_spec.rb index e7235a4e78..372fa2d5e2 100644 --- a/spec/bundler/bundler/definition_spec.rb +++ b/spec/bundler/bundler/definition_spec.rb @@ -193,31 +193,6 @@ RSpec.describe Bundler::Definition do describe "initialize" do context "gem version promoter" do - context "with lockfile" do - before do - install_gemfile <<-G - source "#{file_uri_for(gem_repo1)}" - gem "foo" - G - - allow(Bundler::SharedHelpers).to receive(:find_gemfile).and_return(bundled_app_gemfile) - end - - it "should get a locked specs list when updating all" do - definition = Bundler::Definition.new(bundled_app_lock, [], Bundler::SourceList.new, true) - locked_specs = definition.gem_version_promoter.locked_specs - expect(locked_specs.to_a.map(&:name)).to eq ["foo"] - expect(definition.instance_variable_get("@locked_specs").empty?).to eq true - end - end - - context "without gemfile or lockfile" do - it "should not attempt to parse empty lockfile contents" do - definition = Bundler::Definition.new(nil, [], mock_source_list, true) - expect(definition.gem_version_promoter.locked_specs.to_a).to eq [] - end - end - context "eager unlock" do let(:source_list) do Bundler::SourceList.new.tap do |source_list| diff --git a/spec/bundler/bundler/gem_version_promoter_spec.rb b/spec/bundler/bundler/gem_version_promoter_spec.rb index 54c559c1d8..b6f10be2aa 100644 --- a/spec/bundler/bundler/gem_version_promoter_spec.rb +++ b/spec/bundler/bundler/gem_version_promoter_spec.rb @@ -6,35 +6,32 @@ RSpec.describe Bundler::GemVersionPromoter do result.flatten.map(&:version).map(&:to_s) end - def make_instance(*args) - @gvp = Bundler::GemVersionPromoter.new(*args).tap do |gvp| + def make_instance + @gvp = Bundler::GemVersionPromoter.new.tap do |gvp| gvp.class.class_eval { public :filter_dep_specs, :sort_dep_specs } end end - def unlocking(options) - make_instance(Bundler::SpecSet.new([]), ["foo"]).tap do |p| + def with_options(options) + make_instance.tap do |p| p.level = options[:level] if options[:level] p.strict = options[:strict] if options[:strict] end end - def keep_locked(options) - make_instance(Bundler::SpecSet.new([]), ["bar"]).tap do |p| - p.level = options[:level] if options[:level] - p.strict = options[:strict] if options[:strict] + def build_candidates(versions) + versions.map do |v| + Bundler::Resolver::Candidate.new(v) end end - def build_spec_groups(name, versions) - versions.map do |v| - Bundler::Resolver::SpecGroup.new(build_spec(name, v), [Gem::Platform::RUBY]) - end + def build_spec_set(name, v) + Bundler::SpecSet.new(build_spec(name, v)) end # Rightmost (highest array index) in result is most preferred. # Leftmost (lowest array index) in result is least preferred. - # `build_spec_groups` has all versions of gem in index. + # `build_candidates` has all versions of gem in index. # `build_spec` is the version currently in the .lock file. # # In default (not strict) mode, all versions in the index will @@ -43,28 +40,28 @@ RSpec.describe Bundler::GemVersionPromoter do # would not consider conservative. context "filter specs (strict) level patch" do it "when keeping build_spec, keep current, next release" do - keep_locked(:level => :patch) + with_options(:level => :patch) res = @gvp.filter_dep_specs( - build_spec_groups("foo", %w[1.7.8 1.7.9 1.8.0]), - build_spec("foo", "1.7.8").first + build_candidates(%w[1.7.8 1.7.9 1.8.0]), + Bundler::Resolver::Package.new("foo", [], build_spec_set("foo", "1.7.8"), []) ) - expect(versions(res)).to eq %w[1.7.9 1.7.8] + expect(versions(res)).to match_array %w[1.7.9 1.7.8] end it "when unlocking prefer next release first" do - unlocking(:level => :patch) + with_options(:level => :patch) res = @gvp.filter_dep_specs( - build_spec_groups("foo", %w[1.7.8 1.7.9 1.8.0]), - build_spec("foo", "1.7.8").first + build_candidates(%w[1.7.8 1.7.9 1.8.0]), + Bundler::Resolver::Package.new("foo", [], build_spec_set("foo", "1.7.8"), []) ) expect(versions(res)).to eq %w[1.7.8 1.7.9] end it "when unlocking keep current when already at latest release" do - unlocking(:level => :patch) + with_options(:level => :patch) res = @gvp.filter_dep_specs( - build_spec_groups("foo", %w[1.7.9 1.8.0 2.0.0]), - build_spec("foo", "1.7.9").first + build_candidates(%w[1.7.9 1.8.0 2.0.0]), + Bundler::Resolver::Package.new("foo", [], build_spec_set("foo", "1.7.9"), []) ) expect(versions(res)).to eq %w[1.7.9] end @@ -72,57 +69,57 @@ RSpec.describe Bundler::GemVersionPromoter do context "filter specs (strict) level minor" do it "when unlocking favor next releases, remove minor and major increases" do - unlocking(:level => :minor) + with_options(:level => :minor) res = @gvp.filter_dep_specs( - build_spec_groups("foo", %w[0.2.0 0.3.0 0.3.1 0.9.0 1.0.0 2.0.0 2.0.1]), - build_spec("foo", "0.2.0").first + build_candidates(%w[0.2.0 0.3.0 0.3.1 0.9.0 1.0.0 2.0.0 2.0.1]), + Bundler::Resolver::Package.new("foo", [], build_spec_set("foo", "0.2.0"), []) ) expect(versions(res)).to eq %w[0.2.0 0.3.0 0.3.1 0.9.0] end it "when keep locked, keep current, then favor next release, remove minor and major increases" do - keep_locked(:level => :minor) + with_options(:level => :minor) res = @gvp.filter_dep_specs( - build_spec_groups("foo", %w[0.2.0 0.3.0 0.3.1 0.9.0 1.0.0 2.0.0 2.0.1]), - build_spec("foo", "0.2.0").first + build_candidates(%w[0.2.0 0.3.0 0.3.1 0.9.0 1.0.0 2.0.0 2.0.1]), + Bundler::Resolver::Package.new("foo", [], build_spec_set("foo", "0.2.0"), ["bar"]) ) - expect(versions(res)).to eq %w[0.3.0 0.3.1 0.9.0 0.2.0] + expect(versions(res)).to match_array %w[0.3.0 0.3.1 0.9.0 0.2.0] end end context "sort specs (not strict) level patch" do it "when not unlocking, same order but make sure build_spec version is most preferred to stay put" do - keep_locked(:level => :patch) + with_options(:level => :patch) res = @gvp.sort_dep_specs( - build_spec_groups("foo", %w[1.5.4 1.6.5 1.7.6 1.7.7 1.7.8 1.7.9 1.8.0 1.8.1 2.0.0 2.0.1]), - build_spec("foo", "1.7.7").first + build_candidates(%w[1.5.4 1.6.5 1.7.6 1.7.7 1.7.8 1.7.9 1.8.0 1.8.1 2.0.0 2.0.1]), + Bundler::Resolver::Package.new("foo", [], build_spec_set("foo", "1.7.7"), ["bar"]) ) expect(versions(res)).to eq %w[1.5.4 1.6.5 1.7.6 2.0.0 2.0.1 1.8.0 1.8.1 1.7.8 1.7.9 1.7.7] end it "when unlocking favor next release, then current over minor increase" do - unlocking(:level => :patch) + with_options(:level => :patch) res = @gvp.sort_dep_specs( - build_spec_groups("foo", %w[1.7.7 1.7.8 1.7.9 1.8.0]), - build_spec("foo", "1.7.8").first + build_candidates(%w[1.7.7 1.7.8 1.7.9 1.8.0]), + Bundler::Resolver::Package.new("foo", [], build_spec_set("foo", "1.7.8"), []) ) expect(versions(res)).to eq %w[1.7.7 1.8.0 1.7.8 1.7.9] end it "when unlocking do proper integer comparison, not string" do - unlocking(:level => :patch) + with_options(:level => :patch) res = @gvp.sort_dep_specs( - build_spec_groups("foo", %w[1.7.7 1.7.8 1.7.9 1.7.15 1.8.0]), - build_spec("foo", "1.7.8").first + build_candidates(%w[1.7.7 1.7.8 1.7.9 1.7.15 1.8.0]), + Bundler::Resolver::Package.new("foo", [], build_spec_set("foo", "1.7.8"), []) ) expect(versions(res)).to eq %w[1.7.7 1.8.0 1.7.8 1.7.9 1.7.15] end it "leave current when unlocking but already at latest release" do - unlocking(:level => :patch) + with_options(:level => :patch) res = @gvp.sort_dep_specs( - build_spec_groups("foo", %w[1.7.9 1.8.0 2.0.0]), - build_spec("foo", "1.7.9").first + build_candidates(%w[1.7.9 1.8.0 2.0.0]), + Bundler::Resolver::Package.new("foo", [], build_spec_set("foo", "1.7.9"), []) ) expect(versions(res)).to eq %w[2.0.0 1.8.0 1.7.9] end @@ -130,10 +127,10 @@ RSpec.describe Bundler::GemVersionPromoter do context "sort specs (not strict) level minor" do it "when unlocking favor next release, then minor increase over current" do - unlocking(:level => :minor) + with_options(:level => :minor) res = @gvp.sort_dep_specs( - build_spec_groups("foo", %w[0.2.0 0.3.0 0.3.1 0.9.0 1.0.0 2.0.0 2.0.1]), - build_spec("foo", "0.2.0").first + build_candidates(%w[0.2.0 0.3.0 0.3.1 0.9.0 1.0.0 2.0.0 2.0.1]), + Bundler::Resolver::Package.new("foo", [], build_spec_set("foo", "0.2.0"), []) ) expect(versions(res)).to eq %w[2.0.0 2.0.1 1.0.0 0.2.0 0.3.0 0.3.1 0.9.0] end diff --git a/spec/bundler/bundler/resolver/candidate_spec.rb b/spec/bundler/bundler/resolver/candidate_spec.rb new file mode 100644 index 0000000000..0840f77245 --- /dev/null +++ b/spec/bundler/bundler/resolver/candidate_spec.rb @@ -0,0 +1,10 @@ +# frozen_string_literal: true + +RSpec.describe Bundler::Resolver::Candidate do + it "compares fine" do + version1 = described_class.new("1.12.5", :specs => [Gem::Specification.new("foo", "1.12.5") {|s| s.platform = Gem::Platform::RUBY }]) + version2 = described_class.new("1.12.5") + + expect(version1 >= version2).to be true + end +end diff --git a/spec/bundler/bundler/version_ranges_spec.rb b/spec/bundler/bundler/version_ranges_spec.rb deleted file mode 100644 index bca044b0c0..0000000000 --- a/spec/bundler/bundler/version_ranges_spec.rb +++ /dev/null @@ -1,40 +0,0 @@ -# frozen_string_literal: true - -require "bundler/version_ranges" - -RSpec.describe Bundler::VersionRanges do - describe ".empty?" do - shared_examples_for "empty?" do |exp, *req| - it "returns #{exp} for #{req}" do - r = Gem::Requirement.new(*req) - ranges = described_class.for(r) - expect(described_class.empty?(*ranges)).to eq(exp), "expected `#{r}` #{exp ? "" : "not "}to be empty" - end - end - - include_examples "empty?", false - include_examples "empty?", false, "!= 1" - include_examples "empty?", false, "!= 1", "= 2" - include_examples "empty?", false, "!= 1", "> 1" - include_examples "empty?", false, "!= 1", ">= 1" - include_examples "empty?", false, "= 1", ">= 0.1", "<= 1.1" - include_examples "empty?", false, "= 1", ">= 1", "<= 1" - include_examples "empty?", false, "= 1", "~> 1" - include_examples "empty?", false, ">= 0.z", "= 0" - include_examples "empty?", false, ">= 0" - include_examples "empty?", false, ">= 1.0.0", "< 2.0.0" - include_examples "empty?", false, "~> 1" - include_examples "empty?", false, "~> 2.0", "~> 2.1" - include_examples "empty?", true, ">= 4.1.0", "< 5.0", "= 5.2.1" - include_examples "empty?", true, "< 5.0", "< 5.3", "< 6.0", "< 6", "= 5.2.0", "> 2", ">= 3.0", ">= 3.1", ">= 3.2", ">= 4.0.0", ">= 4.1.0", ">= 4.2.0", ">= 4.2", ">= 4" - include_examples "empty?", true, "!= 1", "< 2", "> 2" - include_examples "empty?", true, "!= 1", "<= 1", ">= 1" - include_examples "empty?", true, "< 2", "> 2" - include_examples "empty?", true, "< 2", "> 2", "= 2" - include_examples "empty?", true, "= 1", "!= 1" - include_examples "empty?", true, "= 1", "= 2" - include_examples "empty?", true, "= 1", "~> 2" - include_examples "empty?", true, ">= 0", "<= 0.a" - include_examples "empty?", true, "~> 2.0", "~> 3" - end -end diff --git a/spec/bundler/install/bundler_spec.rb b/spec/bundler/install/bundler_spec.rb index 963ce82db8..ae7c94c31f 100644 --- a/spec/bundler/install/bundler_spec.rb +++ b/spec/bundler/install/bundler_spec.rb @@ -37,12 +37,11 @@ RSpec.describe "bundle install" do G nice_error = <<-E.strip.gsub(/^ {8}/, "") - Bundler could not find compatible versions for gem "bundler": - In Gemfile: - bundler (= 0.9.1) + Could not find compatible versions - Current Bundler version: - bundler (#{Bundler::VERSION}) + Because the current Bundler version (#{Bundler::VERSION}) does not satisfy bundler = 0.9.1 + and Gemfile depends on bundler = 0.9.1, + version solving has failed. Your bundle requires a different version of Bundler than the one you're running. Install the necessary version with `gem install bundler:0.9.1` and rerun bundler using `bundle _0.9.1_ install` @@ -58,12 +57,14 @@ RSpec.describe "bundle install" do G nice_error = <<-E.strip.gsub(/^ {8}/, "") - Bundler could not find compatible versions for gem "bundler": - In Gemfile: - bundler (~> 0.8) + Could not find compatible versions - Current Bundler version: - bundler (#{Bundler::VERSION}) + Because rails >= 3.0 depends on bundler >= 0.9.0.pre + and the current Bundler version (#{Bundler::VERSION}) does not satisfy bundler >= 0.9.0.pre, < 1.A, + rails >= 3.0 requires bundler >= 1.A. + So, because Gemfile depends on rails = 3.0 + and Gemfile depends on bundler ~> 0.8, + version solving has failed. Your bundle requires a different version of Bundler than the one you're running. Install the necessary version with `gem install bundler:0.9.1` and rerun bundler using `bundle _0.9.1_ install` @@ -79,12 +80,11 @@ RSpec.describe "bundle install" do G nice_error = <<-E.strip.gsub(/^ {8}/, "") - Bundler could not find compatible versions for gem "bundler": - In Gemfile: - bundler (= 0.9.2) + Could not find compatible versions - Current Bundler version: - bundler (#{Bundler::VERSION}) + Because the current Bundler version (#{Bundler::VERSION}) does not satisfy bundler = 0.9.2 + and Gemfile depends on bundler = 0.9.2, + version solving has failed. Your bundle requires a different version of Bundler than the one you're running, and that version could not be found. E @@ -150,13 +150,14 @@ RSpec.describe "bundle install" do G nice_error = <<-E.strip.gsub(/^ {8}/, "") - Bundler could not find compatible versions for gem "activesupport": - In Gemfile: - activemerchant was resolved to 1.0, which depends on - activesupport (>= 2.0.0) - - rails_pinned_to_old_activesupport was resolved to 1.0, which depends on - activesupport (= 1.2.3) + Could not find compatible versions + + Because every version of rails_pinned_to_old_activesupport depends on activesupport = 1.2.3 + and every version of activemerchant depends on activesupport >= 2.0.0, + every version of rails_pinned_to_old_activesupport is incompatible with activemerchant >= 0. + So, because Gemfile depends on activemerchant >= 0 + and Gemfile depends on rails_pinned_to_old_activesupport >= 0, + version solving has failed. E expect(err).to include(nice_error) end @@ -177,12 +178,13 @@ RSpec.describe "bundle install" do G nice_error = <<-E.strip.gsub(/^ {8}/, "") - Bundler could not find compatible versions for gem "activesupport": - In Gemfile: - activesupport (= 2.3.5) + Could not find compatible versions - rails_pinned_to_old_activesupport was resolved to 1.0, which depends on - activesupport (= 1.2.3) + Because every version of rails_pinned_to_old_activesupport depends on activesupport = 1.2.3 + and Gemfile depends on rails_pinned_to_old_activesupport >= 0, + activesupport = 1.2.3 is required. + So, because Gemfile depends on activesupport = 2.3.5, + version solving has failed. E expect(err).to include(nice_error) end diff --git a/spec/bundler/install/gemfile/git_spec.rb b/spec/bundler/install/gemfile/git_spec.rb index fb99c99b2d..636a3daaad 100644 --- a/spec/bundler/install/gemfile/git_spec.rb +++ b/spec/bundler/install/gemfile/git_spec.rb @@ -881,7 +881,7 @@ RSpec.describe "bundle install with git sources" do gem "has_submodule" end G - expect(err).to match(/could not find gem 'submodule/i) + expect(err).to match(%r{submodule >= 0 could not be found in rubygems repository #{file_uri_for(gem_repo1)}/ or installed locally}) expect(the_bundle).not_to include_gems "has_submodule 1.0" end diff --git a/spec/bundler/install/gemfile/sources_spec.rb b/spec/bundler/install/gemfile/sources_spec.rb index d2733993bb..174bac511e 100644 --- a/spec/bundler/install/gemfile/sources_spec.rb +++ b/spec/bundler/install/gemfile/sources_spec.rb @@ -371,7 +371,15 @@ RSpec.describe "bundle install with gems on multiple sources" do it "fails" do bundle :install, :artifice => "compact_index", :raise_on_error => false - expect(err).to include("Could not find gem 'missing', which is required by gem 'depends_on_missing', in any of the sources.") + expect(err).to end_with <<~E.strip + Could not find compatible versions + + Because every version of depends_on_missing depends on missing >= 0 + and missing >= 0 could not be found in any of the sources, + every version of depends_on_missing is forbidden. + So, because Gemfile depends on depends_on_missing >= 0, + version solving has failed. + E end end @@ -425,9 +433,15 @@ RSpec.describe "bundle install with gems on multiple sources" do it "does not find the dependency" do bundle :install, :artifice => "compact_index", :raise_on_error => false - expect(err).to include( - "Could not find gem 'rack', which is required by gem 'depends_on_rack', in rubygems repository https://gem.repo2/ or installed locally." - ) + expect(err).to end_with <<~E.strip + Could not find compatible versions + + Because every version of depends_on_rack depends on rack >= 0 + and rack >= 0 could not be found in rubygems repository https://gem.repo2/ or installed locally, + every version of depends_on_rack is forbidden. + So, because Gemfile depends on depends_on_rack >= 0, + version solving has failed. + E end end diff --git a/spec/bundler/install/gemfile/specific_platform_spec.rb b/spec/bundler/install/gemfile/specific_platform_spec.rb index 98efec396c..1f615ec8a5 100644 --- a/spec/bundler/install/gemfile/specific_platform_spec.rb +++ b/spec/bundler/install/gemfile/specific_platform_spec.rb @@ -370,6 +370,16 @@ RSpec.describe "bundle install with specific platforms" do * sorbet-static-0.5.6433-x86_64-linux ERROR + error_message = <<~ERROR.strip + Could not find compatible versions + + Because every version of sorbet depends on sorbet-static = 0.5.6433 + and sorbet-static = 0.5.6433 could not be found in rubygems repository #{file_uri_for(gem_repo4)}/ or installed locally, + every version of sorbet is forbidden. + So, because Gemfile depends on sorbet = 0.5.6433, + version solving has failed. + ERROR + simulate_platform "arm64-darwin-21" do bundle "lock", :raise_on_error => false end diff --git a/spec/bundler/install/gems/flex_spec.rb b/spec/bundler/install/gems/flex_spec.rb index ed30d2cc35..4bbb2ea038 100644 --- a/spec/bundler/install/gems/flex_spec.rb +++ b/spec/bundler/install/gems/flex_spec.rb @@ -194,11 +194,13 @@ RSpec.describe "bundle flex_install" do bundle "config set force_ruby_platform true" nice_error = <<-E.strip.gsub(/^ {8}/, "") - Could not find gem 'rack (= 1.2)', which is required by gem 'rack-obama (= 2.0)', in rubygems repository #{file_uri_for(gem_repo2)}/ or installed locally. + Could not find compatible versions - The source contains the following gems matching 'rack': - * rack-0.9.1 - * rack-1.0.0 + Because rack-obama >= 2.0 depends on rack = 1.2 + and rack = 1.2 could not be found in rubygems repository #{file_uri_for(gem_repo2)}/ or installed locally, + rack-obama >= 2.0 is forbidden. + So, because Gemfile depends on rack-obama = 2.0, + version solving has failed. E bundle :install, :retry => 0, :raise_on_error => false diff --git a/spec/bundler/install/gems/resolving_spec.rb b/spec/bundler/install/gems/resolving_spec.rb index 7a5307720f..3977122568 100644 --- a/spec/bundler/install/gems/resolving_spec.rb +++ b/spec/bundler/install/gems/resolving_spec.rb @@ -159,7 +159,7 @@ RSpec.describe "bundle install with install-time dependencies" do bundle :install, :env => { "BUNDLER_DEBUG_RESOLVER" => "1", "DEBUG" => "1" } - expect(out).to include("BUNDLER: Starting resolution") + expect(out).to include("Resolving dependencies...") end end @@ -173,7 +173,7 @@ RSpec.describe "bundle install with install-time dependencies" do bundle :install, :env => { "DEBUG_RESOLVER" => "1", "DEBUG" => "1" } - expect(out).to include("BUNDLER: Starting resolution") + expect(out).to include("Resolving dependencies...") end end @@ -187,12 +187,10 @@ RSpec.describe "bundle install with install-time dependencies" do bundle :install, :env => { "DEBUG_RESOLVER_TREE" => "1", "DEBUG" => "1" } - activated_groups = "net_b (1.0) (ruby)" - expect(out).to include(" net_b"). - and include("BUNDLER: Starting resolution"). - and include("BUNDLER: Finished resolution"). - and include("Attempting to activate [#{activated_groups}]") + and include("Resolving dependencies..."). + and include("Solution found after 1 attempts:"). + and include("selecting net_b 1.0") end end end @@ -379,12 +377,12 @@ RSpec.describe "bundle install with install-time dependencies" do it "gives a meaningful error on ruby version mismatches between dependencies" do build_repo4 do build_gem "requires-old-ruby" do |s| - s.required_ruby_version = "< #{RUBY_VERSION}" + s.required_ruby_version = "< #{Gem.ruby_version}" end end build_lib("foo", :path => bundled_app) do |s| - s.required_ruby_version = ">= #{RUBY_VERSION}" + s.required_ruby_version = ">= #{Gem.ruby_version}" s.add_dependency "requires-old-ruby" end @@ -394,7 +392,16 @@ RSpec.describe "bundle install with install-time dependencies" do gemspec G - expect(err).to include("Bundler found conflicting requirements for the Ruby\0 version:") + expect(err).to end_with <<~E.strip + Could not find compatible versions + + Because every version of foo depends on requires-old-ruby >= 0 + and every version of requires-old-ruby depends on Ruby < #{Gem.ruby_version}, + every version of foo requires Ruby < #{Gem.ruby_version}. + So, because Gemfile depends on foo >= 0 + and current Ruby version is = #{Gem.ruby_version}, + version solving has failed. + E end it "installs the older version under rate limiting conditions" do @@ -464,14 +471,13 @@ RSpec.describe "bundle install with install-time dependencies" do expect(out).to_not include("Gem::InstallError: require_ruby requires Ruby version > 9000") nice_error = strip_whitespace(<<-E).strip - Bundler found conflicting requirements for the Ruby\0 version: - In Gemfile: - require_ruby was resolved to 1.0, which depends on - Ruby\0 (> 9000) - - Current Ruby\0 version: - Ruby\0 (#{error_message_requirement}) + Could not find compatible versions + Because every version of require_ruby depends on Ruby > 9000 + and Gemfile depends on require_ruby >= 0, + Ruby > 9000 is required. + So, because current Ruby version is #{error_message_requirement}, + version solving has failed. E expect(err).to end_with(nice_error) end @@ -487,14 +493,13 @@ RSpec.describe "bundle install with install-time dependencies" do expect(out).to_not include("Gem::InstallError: require_ruby requires Ruby version > 9000") nice_error = strip_whitespace(<<-E).strip - Bundler found conflicting requirements for the Ruby\0 version: - In Gemfile: - require_ruby was resolved to 1.0, which depends on - Ruby\0 (> 9000) - - Current Ruby\0 version: - Ruby\0 (#{error_message_requirement}) + Could not find compatible versions + Because every version of require_ruby depends on Ruby > 9000 + and Gemfile depends on require_ruby >= 0, + Ruby > 9000 is required. + So, because current Ruby version is #{error_message_requirement}, + version solving has failed. E expect(err).to end_with(nice_error) end @@ -532,14 +537,11 @@ RSpec.describe "bundle install with install-time dependencies" do expect(err).to_not include("Gem::InstallError: require_rubygems requires RubyGems version > 9000") nice_error = strip_whitespace(<<-E).strip - Bundler found conflicting requirements for the RubyGems\0 version: - In Gemfile: - require_rubygems was resolved to 1.0, which depends on - RubyGems\0 (> 9000) - - Current RubyGems\0 version: - RubyGems\0 (= #{Gem::VERSION}) - + Because every version of require_rubygems depends on RubyGems > 9000 + and Gemfile depends on require_rubygems >= 0, + RubyGems > 9000 is required. + So, because current RubyGems version is = #{Gem::VERSION}, + version solving has failed. E expect(err).to end_with(nice_error) end diff --git a/spec/bundler/realworld/edgecases_spec.rb b/spec/bundler/realworld/edgecases_spec.rb index a98859c2d9..e1bb92d36e 100644 --- a/spec/bundler/realworld/edgecases_spec.rb +++ b/spec/bundler/realworld/edgecases_spec.rb @@ -11,7 +11,8 @@ RSpec.describe "real world edgecases", :realworld => true do source = Bundler::Source::Rubygems::Remote.new(Bundler::URI("https://rubygems.org")) fetcher = Bundler::Fetcher.new(source) index = fetcher.specs([#{name.dump}], nil) - index.search(Gem::Dependency.new(#{name.dump}, #{requirement.dump})).last + requirement = Gem::Requirement.create(#{requirement.dump}) + index.search(#{name.dump}).select {|spec| requirement.satisfied_by?(spec.version) }.last end if rubygem.nil? raise "Could not find #{name} (#{requirement}) on rubygems.org!\n" \ diff --git a/spec/bundler/resolver/basic_spec.rb b/spec/bundler/resolver/basic_spec.rb index b583fb8715..41c6d9972c 100644 --- a/spec/bundler/resolver/basic_spec.rb +++ b/spec/bundler/resolver/basic_spec.rb @@ -104,7 +104,7 @@ RSpec.describe "Resolving" do dep "chef_app_error" expect do resolve - end.to raise_error(Bundler::VersionConflict) + end.to raise_error(Bundler::SolveFailure) end it "raises an exception with the minimal set of conflicting dependencies" do @@ -118,14 +118,15 @@ RSpec.describe "Resolving" do dep "c" expect do resolve - end.to raise_error(Bundler::VersionConflict, <<-E.strip) -Bundler could not find compatible versions for gem "a": - In Gemfile: - b was resolved to 1.0, which depends on - a (>= 2) - - c was resolved to 1.0, which depends on - a (< 1) + end.to raise_error(Bundler::SolveFailure, <<~E.strip) + Could not find compatible versions + + Because every version of c depends on a < 1 + and every version of b depends on a >= 2, + every version of c is incompatible with b >= 0. + So, because Gemfile depends on b >= 0 + and Gemfile depends on c >= 0, + version solving has failed. E end @@ -134,7 +135,7 @@ Bundler could not find compatible versions for gem "a": dep "circular_app" expect do - resolve + Bundler::SpecSet.new(resolve).sort end.to raise_error(Bundler::CyclicDependencyError, /please remove either gem 'bar' or gem 'foo'/i) end diff --git a/spec/bundler/resolver/platform_spec.rb b/spec/bundler/resolver/platform_spec.rb index 418293365c..2d143fd84a 100644 --- a/spec/bundler/resolver/platform_spec.rb +++ b/spec/bundler/resolver/platform_spec.rb @@ -210,39 +210,6 @@ RSpec.describe "Resolving platform craziness" do should_resolve_as %w[foo-1.1.0] end - it "doesn't include gems not needed for none of the platforms" do - @index = build_index do - gem "empyrean", "0.1.0" - gem "coderay", "1.1.2" - gem "method_source", "0.9.0" - - gem "spoon", "0.0.6" do - dep "ffi", ">= 0" - end - - gem "pry", "0.11.3", "java" do - dep "coderay", "~> 1.1.0" - dep "method_source", "~> 0.9.0" - dep "spoon", "~> 0.0" - end - - gem "pry", "0.11.3" do - dep "coderay", "~> 1.1.0" - dep "method_source", "~> 0.9.0" - end - - gem "ffi", "1.9.23", "java" - gem "ffi", "1.9.23" - end - - dep "empyrean", "0.1.0" - dep "pry" - - platforms "ruby", "java" - - should_resolve_as %w[coderay-1.1.2 empyrean-0.1.0 ffi-1.9.23-java method_source-0.9.0 pry-0.11.3 pry-0.11.3-java spoon-0.0.6] - end - it "includes gems needed for at least one platform" do @index = build_index do gem "empyrean", "0.1.0" diff --git a/spec/bundler/runtime/inline_spec.rb b/spec/bundler/runtime/inline_spec.rb index d53e8663a6..fd1dd6dc26 100644 --- a/spec/bundler/runtime/inline_spec.rb +++ b/spec/bundler/runtime/inline_spec.rb @@ -96,12 +96,14 @@ RSpec.describe "bundler/inline#gemfile" do it "lets me use my own ui object" do script <<-RUBY, :artifice => "endpoint" require '#{entrypoint}' - class MyBundlerUI < Bundler::UI::Silent + class MyBundlerUI < Bundler::UI::Shell def confirm(msg, newline = nil) puts "CONFIRMED!" end end - gemfile(true, :ui => MyBundlerUI.new) do + my_ui = MyBundlerUI.new + my_ui.level = "confirm" + gemfile(true, :ui => my_ui) do source "https://notaserver.com" gem "activesupport", :require => true end diff --git a/spec/bundler/support/indexes.rb b/spec/bundler/support/indexes.rb index e20059429c..744dd6e233 100644 --- a/spec/bundler/support/indexes.rb +++ b/spec/bundler/support/indexes.rb @@ -18,15 +18,22 @@ module Spec @platforms ||= ["ruby"] default_source = instance_double("Bundler::Source::Rubygems", :specs => @index, :to_s => "locally install gems") source_requirements = { :default => default_source } - @deps.each do |d| - source_requirements[d.name] = d.source = default_source - end args[0] ||= Bundler::SpecSet.new([]) # base args[0].each {|ls| ls.source = default_source } args[1] ||= Bundler::GemVersionPromoter.new # gem_version_promoter args[2] ||= [] # additional_base_requirements - args[3] ||= @platforms # platforms - Bundler::Resolver.new(source_requirements, *args).start(@deps) + originally_locked = args[3] || Bundler::SpecSet.new([]) + unlock = args[4] || [] + packages = Hash.new do |h, k| + h[k] = Bundler::Resolver::Package.new(k, @platforms, originally_locked, unlock) + end + @deps.each do |d| + name = d.name + platforms = d.gem_platforms(@platforms) + source_requirements[name] = d.source = default_source + packages[name] = Bundler::Resolver::Package.new(name, platforms, originally_locked, unlock, :dependency => d) + end + Bundler::Resolver.new(source_requirements, *args[0..2]).start(@deps, packages) end def should_not_resolve @@ -47,13 +54,6 @@ module Spec end end - def should_conflict_on(names) - got = resolve - raise "The resolve succeeded with: #{got.map(&:full_name).sort.inspect}" - rescue Bundler::VersionConflict => e - expect(Array(names).sort).to eq(e.conflicts.sort) - end - def gem(*args, &blk) build_spec(*args, &blk).first end @@ -67,12 +67,11 @@ module Spec def should_conservative_resolve_and_include(opts, unlock, specs) # empty unlock means unlock all opts = Array(opts) - search = Bundler::GemVersionPromoter.new(@locked, unlock).tap do |s| + search = Bundler::GemVersionPromoter.new.tap do |s| s.level = opts.first s.strict = opts.include?(:strict) - s.prerelease_specified = Hash[@deps.map {|d| [d.name, d.requirement.prerelease?] }] end - should_resolve_and_include specs, [@base, search] + should_resolve_and_include specs, [@base, search, [], @locked, unlock] end def an_awesome_index |