diff options
Diffstat (limited to 'lib/bundler/vendor/pub_grub/lib/pub_grub')
15 files changed, 1904 insertions, 0 deletions
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..239eaf3401 --- /dev/null +++ b/lib/bundler/vendor/pub_grub/lib/pub_grub/incompatibility.rb @@ -0,0 +1,150 @@ +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? + if term.constraint.any? + "#{term.package} cannot be used" + else + "#{term.to_s(allow_every: true)} cannot be used" + end + else + "#{term.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..36ab06254d --- /dev/null +++ b/lib/bundler/vendor/pub_grub/lib/pub_grub/static_package_source.rb @@ -0,0 +1,61 @@ +require_relative 'package' +require_relative 'rubygems' +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] = clean_deps(name, version, deps) + end + + private + + # Exclude redundant self-referencing dependencies + def clean_deps(name, version, deps) + deps.reject {|dep_name, req| name == dep_name && Bundler::PubGrub::RubyGems.parse_range(req).include?(version) } + 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..b71f3eaf53 --- /dev/null +++ b/lib/bundler/vendor/pub_grub/lib/pub_grub/version_constraint.rb @@ -0,0 +1,129 @@ +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 ==(other) + package == other.package && + range == other.range + 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..8d73c3f7b5 --- /dev/null +++ b/lib/bundler/vendor/pub_grub/lib/pub_grub/version_range.rb @@ -0,0 +1,411 @@ +# 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) + 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 + Empty.singleton_class.undef_method(: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) + !other.empty? && + 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.to_s == max.to_s + + 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..4caf6b355b --- /dev/null +++ b/lib/bundler/vendor/pub_grub/lib/pub_grub/version_solver.rb @@ -0,0 +1,248 @@ +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 + logger.debug { "attempting #{package} #{version}" } + + 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 { "selected #{package} #{version}" } + + solution.decide(package, version) + else + logger.info { "conflict: #{conflict.inspect}" } + end + + package + end + + 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 + + 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..bbc10c3804 --- /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.empty? || (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.empty? || (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.to_s == range.max.to_s + 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 |