Class: Bundler::PubGrub::VersionSolver
Relationships & Source Files | |
Inherits: | Object |
Defined in: | lib/bundler/vendor/pub_grub/lib/pub_grub/version_solver.rb |
Class Method Summary
Instance Attribute Summary
- #logger readonly
- #solution readonly
- #solved? ⇒ Boolean readonly
- #source readonly
- #strategy readonly
Instance Method Summary
-
#result
Alias for #solve.
- #solve (also: #result)
-
#work
Returns true if there is more work to be done, false otherwise.
- #add_incompatibility(incompatibility) private
- #choose_package_version_from(unsatisfied_terms) private
- #propagate(initial_package) private
- #propagate_incompatibility(incompatibility) private
- #resolve_conflict(incompatibility) private
Constructor Details
.new(source:, root: Package.root, strategy: Strategy.new(source), logger: Bundler::PubGrub.logger) ⇒ VersionSolver
# File 'lib/bundler/vendor/pub_grub/lib/pub_grub/version_solver.rb', line 14
def initialize(source:, root: Package.root, strategy: Strategy.new(source), logger: Bundler::PubGrub.logger) @logger = logger @source = source @strategy = strategy # { 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
Instance Attribute Details
#logger (readonly)
[ GitHub ]# File 'lib/bundler/vendor/pub_grub/lib/pub_grub/version_solver.rb', line 9
attr_reader :logger
#solution (readonly)
[ GitHub ]# File 'lib/bundler/vendor/pub_grub/lib/pub_grub/version_solver.rb', line 11
attr_reader :solution
#solved? ⇒ Boolean
(readonly)
[ GitHub ]
# File 'lib/bundler/vendor/pub_grub/lib/pub_grub/version_solver.rb', line 36
def solved? solution.unsatisfied.empty? end
#source (readonly)
[ GitHub ]# File 'lib/bundler/vendor/pub_grub/lib/pub_grub/version_solver.rb', line 10
attr_reader :source
#strategy (readonly)
[ GitHub ]# File 'lib/bundler/vendor/pub_grub/lib/pub_grub/version_solver.rb', line 12
attr_reader :strategy
Instance Method Details
#add_incompatibility(incompatibility) (private)
[ GitHub ]# File 'lib/bundler/vendor/pub_grub/lib/pub_grub/version_solver.rb', line 228
def add_incompatibility(incompatibility) logger.debug { "fact: #{incompatibility}" } incompatibility.terms.each do |term| package = term.package @incompatibilities[package] << incompatibility end end
#choose_package_version_from(unsatisfied_terms) (private)
[ GitHub ]# File 'lib/bundler/vendor/pub_grub/lib/pub_grub/version_solver.rb', line 110
def choose_package_version_from(unsatisfied_terms) remaining = unsatisfied_terms.map { |t| [t.package, t.constraint.range] }.to_h package, version = strategy.next_package_and_version(remaining) logger.debug { "attempting #{package} #{version}" } if version.nil? unsatisfied_term = unsatisfied_terms.find { |t| t.package == package } 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 { "selected #{package} #{version}" } solution.decide(package, version) else logger.info { "conflict: #{conflict.inspect}" } end package end
#propagate(initial_package) (private)
[ GitHub ]# File 'lib/bundler/vendor/pub_grub/lib/pub_grub/version_solver.rb', line 69
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
#propagate_incompatibility(incompatibility) (private)
[ GitHub ]# File 'lib/bundler/vendor/pub_grub/lib/pub_grub/version_solver.rb', line 86
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
#resolve_conflict(incompatibility) (private)
# File 'lib/bundler/vendor/pub_grub/lib/pub_grub/version_solver.rb', line 150
def resolve_conflict(incompatibility) logger.info { "conflict: #{incompatibility}" } new_incompatibility = nil 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(new_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 new_incompatibility = Incompatibility.new(new_terms, cause: Incompatibility::ConflictCause.new(incompatibility, most_recent_satisfier.cause)) if incompatibility.to_s == new_incompatibility.to_s logger.info { "!! failed to resolve conflicts, this shouldn't have happened" } break end incompatibility = new_incompatibility 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
#result
Alias for #solve.
# File 'lib/bundler/vendor/pub_grub/lib/pub_grub/version_solver.rb', line 65
alias_method :result, :solve
#solve Also known as: #result
[ GitHub ]#work
Returns true if there is more work to be done, false otherwise
# File 'lib/bundler/vendor/pub_grub/lib/pub_grub/version_solver.rb', line 41
def work unsatisfied_terms = solution.unsatisfied if unsatisfied_terms.empty? 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 return false end next_package = choose_package_version_from(unsatisfied_terms) propagate(next_package) true end