/usr/lib/ruby/vendor_ruby/bundler/resolver.rb is in ruby-bundler 1.16.1-1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 | # frozen_string_literal: true
module Bundler
class Resolver
require "bundler/vendored_molinillo"
require "bundler/resolver/spec_group"
# Figures out the best possible configuration of gems that satisfies
# the list of passed dependencies and any child dependencies without
# causing any gem activation errors.
#
# ==== Parameters
# *dependencies<Gem::Dependency>:: The list of dependencies to resolve
#
# ==== Returns
# <GemBundle>,nil:: If the list of dependencies can be resolved, a
# collection of gemspecs is returned. Otherwise, nil is returned.
def self.resolve(requirements, index, source_requirements = {}, base = [], gem_version_promoter = GemVersionPromoter.new, additional_base_requirements = [], platforms = nil)
platforms = Set.new(platforms) if platforms
base = SpecSet.new(base) unless base.is_a?(SpecSet)
resolver = new(index, source_requirements, base, gem_version_promoter, additional_base_requirements, platforms)
result = resolver.start(requirements)
SpecSet.new(result)
end
def initialize(index, source_requirements, base, gem_version_promoter, additional_base_requirements, platforms)
@index = index
@source_requirements = source_requirements
@base = base
@resolver = Molinillo::Resolver.new(self, self)
@search_for = {}
@base_dg = Molinillo::DependencyGraph.new
@base.each do |ls|
dep = Dependency.new(ls.name, ls.version)
@base_dg.add_vertex(ls.name, DepProxy.new(dep, ls.platform), true)
end
additional_base_requirements.each {|d| @base_dg.add_vertex(d.name, d) }
@platforms = platforms
@gem_version_promoter = gem_version_promoter
@allow_bundler_dependency_conflicts = Bundler.feature_flag.allow_bundler_dependency_conflicts?
@lockfile_uses_separate_rubygems_sources = Bundler.feature_flag.lockfile_uses_separate_rubygems_sources?
end
def start(requirements)
@prerelease_specified = {}
requirements.each {|dep| @prerelease_specified[dep.name] ||= dep.prerelease? }
verify_gemfile_dependencies_are_found!(requirements)
dg = @resolver.resolve(requirements, @base_dg)
dg.map(&:payload).
reject {|sg| sg.name.end_with?("\0") }.
map(&:to_specs).flatten
rescue Molinillo::VersionConflict => e
message = version_conflict_message(e)
raise VersionConflict.new(e.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."
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)
STDERR.puts debug_info.split("\n").map {|s| " " * depth + s }
end
def debug?
return @debug_mode if defined?(@debug_mode)
@debug_mode = ENV["DEBUG_RESOLVER"] || ENV["DEBUG_RESOLVER_TREE"] || false
end
def before_resolution
Bundler.ui.info "Resolving dependencies...", debug?
end
def after_resolution
Bundler.ui.info ""
end
def indicate_progress
Bundler.ui.info ".", false unless debug?
end
include Molinillo::SpecificationProvider
def dependencies_for(specification)
specification.dependencies_for_activated_platforms
end
def search_for(dependency)
platform = dependency.__platform
dependency = dependency.dep unless dependency.is_a? Gem::Dependency
search = @search_for[dependency] ||= begin
index = index_for(dependency)
results = index.search(dependency, @base[dependency.name])
unless @prerelease_specified[dependency.name]
# Move prereleases to the beginning of the list, so they're considered
# last during resolution.
pre, results = results.partition {|spec| spec.version.prerelease? }
results = pre + results
end
if vertex = @base_dg.vertex_named(dependency.name)
locked_requirement = vertex.payload.requirement
end
spec_groups = if results.any?
nested = []
results.each do |spec|
version, specs = nested.last
if version == spec.version
specs << spec
else
nested << [spec.version, [spec]]
end
end
nested.reduce([]) do |groups, (version, specs)|
next groups if locked_requirement && !locked_requirement.satisfied_by?(version)
spec_group = SpecGroup.new(specs)
spec_group.ignores_bundler_dependencies = @allow_bundler_dependency_conflicts
groups << spec_group
end
else
[]
end
# GVP handles major itself, but it's still a bit risky to trust it with it
# until we get it settled with new behavior. For 2.x it can take over all cases.
if @gem_version_promoter.major?
spec_groups
else
@gem_version_promoter.sort_versions(dependency, spec_groups)
end
end
search.select {|sg| sg.for?(platform) }.each {|sg| sg.activate_platform!(platform) }
end
def index_for(dependency)
source = @source_requirements[dependency.name]
if source
source.specs
elsif @lockfile_uses_separate_rubygems_sources
Index.build do |idx|
if dependency.all_sources
dependency.all_sources.each {|s| idx.add_source(s.specs) if s }
else
idx.add_source @source_requirements[:default].specs
end
end
else
@index
end
end
def name_for(dependency)
dependency.name
end
def name_for_explicit_dependency_source
Bundler.default_gemfile.basename.to_s
rescue
"Gemfile"
end
def name_for_locking_dependency_source
Bundler.default_lockfile.basename.to_s
rescue
"Gemfile.lock"
end
def requirement_satisfied_by?(requirement, activated, spec)
return false unless requirement.matches_spec?(spec) || spec.source.is_a?(Source::Gemspec)
if spec.version.prerelease? && !requirement.prerelease? && search_for(requirement).any? {|sg| !sg.version.prerelease? }
vertex = activated.vertex_named(spec.name)
return false if vertex.requirements.none?(&:prerelease?)
end
spec.activate_platform!(requirement.__platform) if !@platforms || @platforms.include?(requirement.__platform)
true
end
def relevant_sources_for_vertex(vertex)
if vertex.root?
[@source_requirements[vertex.name]]
elsif @lockfile_uses_separate_rubygems_sources
vertex.recursive_predecessors.map do |v|
@source_requirements[v.name]
end << @source_requirements[:default]
end
end
def sort_dependencies(dependencies, activated, conflicts)
dependencies.sort_by do |dependency|
dependency.all_sources = relevant_sources_for_vertex(activated.vertex_named(dependency.name))
name = name_for(dependency)
vertex = activated.vertex_named(name)
[
@base_dg.vertex_named(name) ? 0 : 1,
vertex.payload ? 0 : 1,
vertex.root? ? 0 : 1,
amount_constrained(dependency),
conflicts[name] ? 0 : 1,
vertex.payload ? 0 : search_for(dependency).count,
self.class.platform_sort_key(dependency.__platform),
]
end
end
# Sort platforms from most general to most specific
def self.sort_platforms(platforms)
platforms.sort_by do |platform|
platform_sort_key(platform)
end
end
def self.platform_sort_key(platform)
return ["", "", ""] if Gem::Platform::RUBY == platform
platform.to_a.map {|part| part || "" }
end
private
# 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] ||= begin
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
end
def verify_gemfile_dependencies_are_found!(requirements)
requirements.each do |requirement|
name = requirement.name
next if name == "bundler"
next unless search_for(requirement).empty?
cache_message = begin
" or in gems cached in #{Bundler.settings.app_cache_path}" if Bundler.app_cache.exist?
rescue GemfileNotFound
nil
end
if (base = @base[name]) && !base.empty?
version = base.first.version
message = "You have requested:\n" \
" #{name} #{requirement.requirement}\n\n" \
"The bundle currently has #{name} locked at #{version}.\n" \
"Try running `bundle update #{name}`\n\n" \
"If you are updating multiple gems in your Gemfile at once,\n" \
"try passing them all to `bundle update`"
elsif source = @source_requirements[name]
specs = source.specs[name]
versions_with_platforms = specs.map {|s| [s.version, s.platform] }
message = String.new("Could not find gem '#{SharedHelpers.pretty_dependency(requirement)}' in #{source}#{cache_message}.\n")
message << if versions_with_platforms.any?
"The source contains '#{name}' at: #{formatted_versions_with_platforms(versions_with_platforms)}"
else
"The source does not contain any versions of '#{name}'"
end
else
message = "Could not find gem '#{requirement}' in any of the gem sources " \
"listed in your Gemfile#{cache_message}."
end
raise GemNotFound, message
end
end
def formatted_versions_with_platforms(versions_with_platforms)
version_platform_strs = versions_with_platforms.map do |vwp|
version = vwp.first
platform = vwp.last
version_platform_str = String.new(version.to_s)
version_platform_str << " #{platform}" unless platform.nil? || platform == Gem::Platform::RUBY
version_platform_str
end
version_platform_strs.join(", ")
end
def version_conflict_message(e)
e.message_with_trees(
:solver_name => "Bundler",
:possibility_type => "gem",
:reduce_trees => lambda do |trees|
# bail out if tree size is too big for Array#combination to make any sense
return trees 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)
trees.reject! {|t| !maximal.include?(t.last) } if maximal
trees = trees.sort_by {|t| t.flatten.map(&:to_s) }
trees.uniq! {|t| t.flatten.map {|dep| [dep.name, dep.requirement] } }
trees.sort_by {|t| t.reverse.map(&:name) }
end,
:printable_requirement => lambda {|req| SharedHelpers.pretty_dependency(req) },
:additional_message_for_conflict => lambda do |o, name, conflict|
if name == "bundler"
o << %(\n Current Bundler version:\n bundler (#{Bundler::VERSION}))
other_bundler_required = !conflict.requirement.requirement.satisfied_by?(Gem::Version.new Bundler::VERSION)
end
if name == "bundler" && other_bundler_required
o << "\n"
o << "This Gemfile requires a different version of Bundler.\n"
o << "Perhaps you need to update Bundler by running `gem install bundler`?\n"
end
if conflict.locked_requirement
o << "\n"
o << %(Running `bundle update` will rebuild your snapshot from scratch, using only\n)
o << %(the gems in your Gemfile, which may resolve the conflict.\n)
elsif !conflict.existing
o << "\n"
relevant_sources = if conflict.requirement.source
[conflict.requirement.source]
elsif conflict.requirement.all_sources
conflict.requirement.all_sources
elsif @lockfile_uses_separate_rubygems_sources
# every conflict should have an explicit group of sources when we
# enforce strict pinning
raise "no source set for #{conflict}"
else
[]
end.compact.map(&:to_s).uniq.sort
o << "Could not find gem '#{SharedHelpers.pretty_dependency(conflict.requirement)}'"
if conflict.requirement_trees.first.size > 1
o << ", which is required by "
o << "gem '#{SharedHelpers.pretty_dependency(conflict.requirement_trees.first[-2])}',"
end
o << " "
o << if relevant_sources.empty?
"in any of the sources.\n"
else
"in any of the relevant sources:\n #{relevant_sources * "\n "}\n"
end
end
end,
:version_for_spec => lambda {|spec| spec.version }
)
end
end
end
|