From b2e0d9707b53a7d799a1dd089ff7e479abacb5fb Mon Sep 17 00:00:00 2001 From: "Samuel E. Giddins" Date: Sun, 16 Nov 2014 20:26:34 -0800 Subject: [Resolver] Update molinillo to the double backjumping branch --- .../Molinillo-double-backjumping/lib/molinillo.rb | 5 + .../lib/molinillo/dependency_graph.rb | 244 +++++++++++ .../lib/molinillo/errors.rb | 69 ++++ .../lib/molinillo/gem_metadata.rb | 3 + .../molinillo/modules/specification_provider.rb | 90 ++++ .../lib/molinillo/modules/ui.rb | 64 +++ .../lib/molinillo/resolution.rb | 454 +++++++++++++++++++++ .../lib/molinillo/resolver.rb | 43 ++ .../lib/molinillo/state.rb | 43 ++ .../vendor/Molinillo-master/lib/molinillo.rb | 5 - .../lib/molinillo/dependency_graph.rb | 244 ----------- .../Molinillo-master/lib/molinillo/errors.rb | 69 ---- .../Molinillo-master/lib/molinillo/gem_metadata.rb | 3 - .../molinillo/modules/specification_provider.rb | 90 ---- .../Molinillo-master/lib/molinillo/modules/ui.rb | 64 --- .../Molinillo-master/lib/molinillo/resolution.rb | 339 --------------- .../Molinillo-master/lib/molinillo/resolver.rb | 43 -- .../vendor/Molinillo-master/lib/molinillo/state.rb | 43 -- lib/bundler/vendored_molinillo.rb | 2 +- 19 files changed, 1016 insertions(+), 901 deletions(-) create mode 100644 lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo.rb create mode 100644 lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/dependency_graph.rb create mode 100644 lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/errors.rb create mode 100644 lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/gem_metadata.rb create mode 100644 lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/modules/specification_provider.rb create mode 100644 lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/modules/ui.rb create mode 100644 lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/resolution.rb create mode 100644 lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/resolver.rb create mode 100644 lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/state.rb delete mode 100644 lib/bundler/vendor/Molinillo-master/lib/molinillo.rb delete mode 100644 lib/bundler/vendor/Molinillo-master/lib/molinillo/dependency_graph.rb delete mode 100644 lib/bundler/vendor/Molinillo-master/lib/molinillo/errors.rb delete mode 100644 lib/bundler/vendor/Molinillo-master/lib/molinillo/gem_metadata.rb delete mode 100644 lib/bundler/vendor/Molinillo-master/lib/molinillo/modules/specification_provider.rb delete mode 100644 lib/bundler/vendor/Molinillo-master/lib/molinillo/modules/ui.rb delete mode 100644 lib/bundler/vendor/Molinillo-master/lib/molinillo/resolution.rb delete mode 100644 lib/bundler/vendor/Molinillo-master/lib/molinillo/resolver.rb delete mode 100644 lib/bundler/vendor/Molinillo-master/lib/molinillo/state.rb (limited to 'lib/bundler') diff --git a/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo.rb b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo.rb new file mode 100644 index 00000000..bf740e48 --- /dev/null +++ b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo.rb @@ -0,0 +1,5 @@ +require 'molinillo/gem_metadata' +require 'molinillo/errors' +require 'molinillo/resolver' +require 'molinillo/modules/ui' +require 'molinillo/modules/specification_provider' diff --git a/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/dependency_graph.rb b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/dependency_graph.rb new file mode 100644 index 00000000..9679222a --- /dev/null +++ b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/dependency_graph.rb @@ -0,0 +1,244 @@ +require 'set' + +module Bundler::Molinillo + # A directed acyclic graph that is tuned to hold named dependencies + class DependencyGraph + include Enumerable + + def each + vertices.values.each { |v| yield v } + 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 [Array] requirements The requirements the directed edge represents + Edge = Struct.new(:origin, :destination, :requirements) + + # @return [{String => Vertex}] vertices that have no {Vertex#predecessors}, + # keyed by by {Vertex#name} + attr_reader :root_vertices + # @return [{String => Vertex}] the vertices of the dependency graph, keyed + # by {Vertex#name} + attr_reader :vertices + # @return [Set] the edges of the dependency graph + attr_reader :edges + + def initialize + @vertices = {} + @edges = Set.new + @root_vertices = {} + end + + # Initializes a copy of a {DependencyGraph}, ensuring that all {#vertices} + # have the correct {Vertex#graph} set + def initialize_copy(other) + super + @vertices = other.vertices.reduce({}) do |vertices, (name, vertex)| + vertices.tap do |hash| + hash[name] = vertex.dup.tap { |v| v.graph = self } + end + end + @root_vertices = Hash[vertices.select { |n, _v| other.root_vertices[n] }] + @edges = other.edges.map do |edge| + Edge.new( + vertex_named(edge.origin.name), + vertex_named(edge.destination.name), + edge.requirements.dup + ) + end + end + + # @return [String] a string suitable for debugging + def inspect + "#{self.class}:#{vertices.values.inspect}" + end + + # @return [Boolean] whether the two dependency graphs are equal, determined + # by a recursive traversal of each {#root_vertices} and its + # {Vertex#successors} + def ==(other) + root_vertices == other.root_vertices + end + + # @param [String] name + # @param [Object] payload + # @param [Array] parent_names + # @param [Object] requirement the requirement that is requiring the child + # @return [void] + def add_child_vertex(name, payload, parent_names, requirement) + is_root = parent_names.include?(nil) + parent_nodes = parent_names.compact.map { |n| vertex_named(n) } + vertex = vertex_named(name) || if is_root + add_root_vertex(name, payload) + else + add_vertex(name, payload) + end + vertex.payload ||= payload + parent_nodes.each do |parent_node| + add_edge(parent_node, vertex, requirement) + end + vertex + end + + # @param [String] name + # @param [Object] payload + # @return [Vertex] the vertex that was added to `self` + def add_vertex(name, payload) + vertex = vertices[name] ||= Vertex.new(self, name, payload) + vertex.tap { |v| v.payload = payload } + end + + # @param [String] name + # @param [Object] payload + # @return [Vertex] the vertex that was added to `self` + def add_root_vertex(name, payload) + add_vertex(name, payload).tap { |v| root_vertices[name] = v } + 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 [void] + def detach_vertex_named(name) + vertex = vertex_named(name) + return unless vertex + successors = vertex.successors + vertices.delete(name) + edges.reject! { |e| e.origin == vertex || e.destination == vertex } + successors.each { |v| detach_vertex_named(v.name) unless root_vertices[v.name] || v.predecessors.any? } + 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) + root_vertices[name] + 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 origin == destination || destination.path_to?(origin) + raise CircularDependencyError.new([origin, destination]) + end + Edge.new(origin, destination, [requirement]).tap { |e| edges << e } + end + + # A vertex in a {DependencyGraph} that encapsulates a {#name} and a + # {#payload} + class Vertex + # @return [DependencyGraph] the graph this vertex is a node of + attr_accessor :graph + + # @return [String] the name of the vertex + attr_accessor :name + + # @return [Object] the payload the vertex holds + attr_accessor :payload + + # @return [Arrary] the explicit requirements that required + # this vertex + attr_reader :explicit_requirements + + # @param [DependencyGraph] graph see {#graph} + # @param [String] name see {#name} + # @param [Object] payload see {#payload} + def initialize(graph, name, payload) + @graph = graph + @name = name + @payload = payload + @explicit_requirements = [] + end + + # @return [Array] all of the requirements that required + # this vertex + def requirements + (incoming_edges.map(&:requirements) + explicit_requirements).flatten + end + + # @return [Array] the edges of {#graph} that have `self` as their + # {Edge#origin} + def outgoing_edges + graph.edges.select { |e| e.origin.shallow_eql?(self) } + end + + # @return [Array] the edges of {#graph} that have `self` as their + # {Edge#destination} + def incoming_edges + graph.edges.select { |e| e.destination.shallow_eql?(self) } + end + + # @return [Set] the vertices of {#graph} that have an edge with + # `self` as their {Edge#destination} + def predecessors + incoming_edges.map(&:origin).to_set + end + + # @return [Set] the vertices of {#graph} that have an edge with + # `self` as their {Edge#origin} + def successors + outgoing_edges.map(&:destination).to_set + end + + # @return [Set] the vertices of {#graph} where `self` is an + # {#ancestor?} + def recursive_successors + successors + successors.map(&:recursive_successors).reduce(Set.new, &:+) + end + + # @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) + shallow_eql?(other) && + successors == other.successors + end + + # @return [Boolean] whether the two vertices are equal, determined + # solely by {#name} and {#payload} equality + def shallow_eql?(other) + other && + name == other.name && + payload == other.payload + end + + alias_method :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 true iff there is a path following edges within this {#graph} + def path_to?(other) + successors.include?(other) || successors.any? { |v| v.path_to?(other) } + end + + alias_method :descendent?, :path_to? + + # Is there a path from `other` to `self` following edges in the + # dependency graph? + # @return true iff there is a path following edges within this {#graph} + def ancestor?(other) + predecessors.include?(other) || predecessors.any? { |v| v.ancestor?(other) } + end + + alias_method :is_reachable_from?, :ancestor? + end + end +end diff --git a/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/errors.rb b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/errors.rb new file mode 100644 index 00000000..b828d0c2 --- /dev/null +++ b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/errors.rb @@ -0,0 +1,69 @@ +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] the specifications that depended upon {#dependency} + attr_accessor :required_by + + # @param [Object] dependency @see {#dependency} + # @param [Array] required_by @see {#required_by} + def initialize(dependency, required_by = []) + @dependency = dependency + @required_by = required_by + super() + end + + 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 iff a {Vertex} is added to a + # {DependencyGraph} that has a {DependencyGraph::Vertex#path_to?} an + # existing {DependencyGraph::Vertex} + class CircularDependencyError < ResolverError + # [Set] the dependencies responsible for causing the error + attr_reader :dependencies + + # @param [Array] nodes the nodes in the dependency + # that caused the error + def initialize(nodes) + super "There is a circular dependency between #{nodes.map(&:name).join(' and ')}" + @dependencies = nodes.map(&:payload).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 + + # @param [{String => Resolution::Conflict}] conflicts see {#conflicts} + def initialize(conflicts) + pairs = [] + conflicts.values.flatten.map(&:requirements).flatten.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 + end + end +end diff --git a/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/gem_metadata.rb b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/gem_metadata.rb new file mode 100644 index 00000000..7c5a03fa --- /dev/null +++ b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/gem_metadata.rb @@ -0,0 +1,3 @@ +module Bundler::Molinillo + VERSION = '0.1.1' +end diff --git a/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/modules/specification_provider.rb b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/modules/specification_provider.rb new file mode 100644 index 00000000..79a85e77 --- /dev/null +++ b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/modules/specification_provider.rb @@ -0,0 +1,90 @@ +module Bundler::Molinillo + # Provides information about specifcations 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] 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] 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 + + # 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] dependencies + # @param [DependencyGraph] activated the current dependency graph in the + # resolution process. + # @param [{String => Array}] conflicts + # @return [Array] 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 + end +end diff --git a/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/modules/ui.rb b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/modules/ui.rb new file mode 100644 index 00000000..fce3290d --- /dev/null +++ b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/modules/ui.rb @@ -0,0 +1,64 @@ +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. + # By default, prints to `STDERR` instead of {#output}. + # + # @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) + STDERR.puts debug_info.split("\n").map { |s| ' ' * depth + s } + 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? + @debug_mode ||= ENV['MOLINILLO_DEBUG'] + end + end +end diff --git a/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/resolution.rb b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/resolution.rb new file mode 100644 index 00000000..743b1629 --- /dev/null +++ b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/resolution.rb @@ -0,0 +1,454 @@ +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 the spec that was unable to be activated due + # to a conflict + # @attr [Object] locked_requirement the relevant locking requirement. + # @attr [Array>] requirement_trees the different requirement + # trees that led to every requirement for the conflicting name. + Conflict = Struct.new( + :requirement, + :requirements, + :existing, + :possibility, + :locked_requirement, + :requirement_trees + ) + + # @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 + + # @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 + @all_conflicts = [] + 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 unless state.requirements.any? || state.requirement + 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 { |s| states.push(s) if s } + end + process_topmost_state + end + + double_check_conflict_existing_specs + + activated.freeze + ensure + end_resolution + end + + private + + # Sets up the resolution process + # @return [void] + def start_resolution + @started_at = Time.now + + states.push(initial_state) + + debug { "Starting resolution (#{@started_at})" } + resolver_ui.before_resolution + 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 'molinillo/state' + require 'molinillo/modules/specification_provider' + + # @return [Integer] the number of resolver iterations in between calls to + # {#resolver_ui}'s {UI#indicate_progress} method + attr_accessor :iteration_rate + + # @return [Time] the time at which resolution began + attr_accessor :started_at + + # @return [Array] the stack of states for the resolution + attr_accessor :states + + # @return [Array] an array of duples of name and + # existing spec for all conflicts. + attr_accessor :all_conflicts + + ResolutionState.new.members.each do |member| + define_method member do |*args, &block| + state.send(member, *args, &block) + end + end + + SpecificationProvider.instance_methods(false).each do |instance_method| + define_method instance_method do |*args, &block| + begin + specification_provider.send(instance_method, *args, &block) + 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 + + # Processes the topmost available {RequirementState} on the stack + # @return [void] + def process_topmost_state + if possibility + attempt_to_activate + else + create_conflict if state.is_a? PossibilityState + unwind_for_conflict until possibility && state.is_a?(DependencyState) + end + 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 the initial state for the resolution, based upon the + # {#requested} dependencies + # @return [DependencyState] the initial state for the resolution + def initial_state + graph = DependencyGraph.new.tap do |dg| + original_requested.each { |r| dg.add_root_vertex(name_for(r), nil).tap { |v| v.explicit_requirements << r } } + end + + requirements = sort_dependencies(original_requested, graph, {}) + initial_requirement = requirements.shift + DependencyState.new( + initial_requirement && name_for(initial_requirement), + requirements, + graph, + initial_requirement, + initial_requirement && search_for(initial_requirement), + 0, + {} + ) + end + + # Unwinds the states stack because a conflict has been encountered + # @return [void] + def unwind_for_conflict + debug(depth) { "Unwinding for conflict: #{requirement}" } + conflicts.tap do |c| + states.slice!((state_index_for_unwind + 1)..-1) + raise VersionConflict.new(c) unless state + state.conflicts = c + end + end + + # @return [Integer] The index to which the resolution should unwind in the + # case of conflict. + def state_index_for_unwind + current_requirement = requirement + existing_requirement = requirement_for_existing_name(name) + until current_requirement.nil? && existing_requirement.nil? + current_state = find_state_for(current_requirement) + existing_state = find_state_for(existing_requirement) + return states.index(current_state) if state_any?(current_state) + return states.index(existing_state) if state_any?(existing_state) + existing_requirement = parent_of(existing_requirement) + current_requirement = parent_of(current_requirement) + end + -1 + end + + # @return [Object] the requirement that led to `requirement` being added + # to the list of requirements. + def parent_of(requirement) + return nil unless requirement + seen = false + state = states.reverse_each.find do |s| + seen ||= s.requirement == requirement + seen && s.requirement != requirement && !s.requirements.include?(requirement) + end + state && state.requirement + end + + # @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 activated.vertex_named(name).payload + states.reverse_each.find { |s| !s.activated.vertex_named(name).payload }.requirement + end + + # @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 + + # @return [Boolean] whether or not the given state has any possibilities + # left. + def state_any?(state) + state && state.possibilities.any? + end + + # Enumerate over {#all_conflicts} and ensure that already activated specs + # that were backtracked from were not that optimal possibilities that + # should have been activated instead, and swaps them in if such a simple + # switch is possible. + # @return [void] + def double_check_conflict_existing_specs + debug { "Double checking conflicts' existing specs" } + all_conflicts.each do |name, conflict_possibility| + next unless conflict_possibility + vertex = activated.vertex_named(name) + possibilities = search_for(vertex.requirements.first) + conflict_index = possibilities.index(conflict_possibility) + payload_index = possibilities.index(vertex.payload) + if conflict_index && payload_index && conflict_index > payload_index + if safe_to_swap?(name, conflict_possibility) + debug { "Swapping #{conflict_possibility} in for #{activated.vertex_named(name).payload}" } + vertex.payload = conflict_possibility + end + end + end + end + + # @param [String] name + # @param [Object] conflict_possibility the existing possibility from a + # conflict that is being attempted to be swapped for the current + # activated spec of the given name. + # @return [Boolen] whether it is safe to swap in `conflict possibility`. + def safe_to_swap?(name, conflict_possibility) + duplicate_activated = activated.dup + duplicate_activated.vertex_named(name).payload = conflict_possibility + locked_requirement = locked_requirement_named(name) + (!locked_requirement || requirement_satisfied_by?(locked_requirement, a, conflict_possibility)) && + activated.vertex_named(name).requirements.all? do |r| + requirement_satisfied_by?(r, duplicate_activated, conflict_possibility) + end && + dependencies_for(conflict_possibility).all? { |r| existing_spec_satisfied_by?(r, duplicate_activated) } + end + + # @param [Object] requirement the requirement. + # @param [DependencyGraph] duplicate_activated the dependency graph that + # should be used when checking for satisfaction. + # @return [Boolean] whether the existing spec satisfies the given + # requirement. + def existing_spec_satisfied_by?(requirement, duplicate_activated) + name = name_for(requirement) + activated.vertex_named(name) && payload = activated.vertex_named(name).payload + payload && requirement_satisfied_by(requirement, duplicate_activated, payload) + end + + # @return [Conflict] a {Conflict} that reflects the failure to activate + # the {#possibility} in conjunction with the current {#state} + def create_conflict + vertex = activated.vertex_named(name) + requirements = { + name_for_explicit_dependency_source => vertex.explicit_requirements, + name_for_locking_dependency_source => Array(locked_requirement_named(name)), + } + vertex.incoming_edges.each { |edge| (requirements[edge.origin.payload] ||= []).unshift(*edge.requirements) } + all_conflicts << [name, vertex.payload] + conflicts[name] = Conflict.new( + requirement, + Hash[requirements.select { |_, r| !r.empty? }], + vertex.payload, + possibility, + locked_requirement_named(name), + requirement_trees + ) + end + + # @return [Array>] rhe different requirement + # trees that led to every requirement for the current spec. + def requirement_trees + activated.vertex_named(name).requirements.map { |r| requirement_tree_for(r) } + end + + # @return [Array] 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_node = activated.vertex_named(name) + if existing_node.payload + debug(depth) { "Found existing spec (#{existing_node.payload})" } + attempt_to_activate_existing_spec(existing_node) + else + attempt_to_activate_new_spec + end + end + + # Attempts to activate the current {#possibility} (given that it has + # already been activated) + # @return [void] + def attempt_to_activate_existing_spec(existing_node) + existing_spec = existing_node.payload + if requirement_satisfied_by?(requirement, activated, existing_spec) + new_requirements = requirements.dup + push_state_for_requirements(new_requirements) + else + create_conflict + debug(depth) { "Unsatisfied by existing spec (#{existing_node.payload})" } + unwind_for_conflict + end + end + + # Attempts to activate the current {#possibility} (given that it hasn't + # already been activated) + # @return [void] + def attempt_to_activate_new_spec + satisfied = begin + locked_requirement = locked_requirement_named(name) + requested_spec_satisfied = requirement_satisfied_by?(requirement, activated, possibility) + locked_spec_satisfied = !locked_requirement || + requirement_satisfied_by?(locked_requirement, activated, possibility) + debug(depth) { 'Unsatisfied by requested spec' } unless requested_spec_satisfied + debug(depth) { 'Unsatisfied by locked spec' } unless locked_spec_satisfied + requested_spec_satisfied && locked_spec_satisfied + end + if satisfied + activate_spec + else + create_conflict + unwind_for_conflict + end + 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_spec + conflicts.delete(name) + debug(depth) { 'Activated ' + name + ' at ' + possibility.to_s } + vertex = activated.vertex_named(name) + vertex.payload = possibility + require_nested_dependencies_for(possibility) + end + + # Requires the dependencies that the recently activated spec has + # @param [Object] activated_spec the specification that has just been + # activated + # @return [void] + def require_nested_dependencies_for(activated_spec) + nested_dependencies = dependencies_for(activated_spec) + debug(depth) { "Requiring nested dependencies (#{nested_dependencies.map(&:to_s).join(', ')})" } + nested_dependencies.each { |d| activated.add_child_vertex name_for(d), nil, [name_for(activated_spec)], d } + + push_state_for_requirements(requirements + nested_dependencies) + end + + # Pushes a new {DependencyState} that encapsulates both existing and new + # requirements + # @param [Array] new_requirements + # @return [void] + def push_state_for_requirements(new_requirements) + new_requirements = sort_dependencies(new_requirements, activated, conflicts) + new_requirement = new_requirements.shift + states.push DependencyState.new( + new_requirement ? name_for(new_requirement) : '', + new_requirements, + activated.dup, + new_requirement, + new_requirement ? search_for(new_requirement) : [], + depth, + conflicts.dup + ) + end + end + end +end diff --git a/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/resolver.rb b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/resolver.rb new file mode 100644 index 00000000..7cfe914d --- /dev/null +++ b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/resolver.rb @@ -0,0 +1,43 @@ +require 'molinillo/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 the {#specification_provider} + # + # + class Resolver + require 'molinillo/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 + + # @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-double-backjumping/lib/molinillo/state.rb b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/state.rb new file mode 100644 index 00000000..8e394f86 --- /dev/null +++ b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/state.rb @@ -0,0 +1,43 @@ +module Bundler::Molinillo + # A state that a {Resolution} can be in + # @attr [String] name + # @attr [Array] requirements + # @attr [DependencyGraph] activated + # @attr [Object] requirement + # @attr [Object] possibility + # @attr [Integer] depth + # @attr [Set] conflicts + ResolutionState = Struct.new( + :name, + :requirements, + :activated, + :requirement, + :possibilities, + :depth, + :conflicts + ) + + # 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.dup, + requirement, + [possibilities.pop], + depth + 1, + conflicts.dup + ) + 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/Molinillo-master/lib/molinillo.rb b/lib/bundler/vendor/Molinillo-master/lib/molinillo.rb deleted file mode 100644 index bf740e48..00000000 --- a/lib/bundler/vendor/Molinillo-master/lib/molinillo.rb +++ /dev/null @@ -1,5 +0,0 @@ -require 'molinillo/gem_metadata' -require 'molinillo/errors' -require 'molinillo/resolver' -require 'molinillo/modules/ui' -require 'molinillo/modules/specification_provider' diff --git a/lib/bundler/vendor/Molinillo-master/lib/molinillo/dependency_graph.rb b/lib/bundler/vendor/Molinillo-master/lib/molinillo/dependency_graph.rb deleted file mode 100644 index 53e09ac7..00000000 --- a/lib/bundler/vendor/Molinillo-master/lib/molinillo/dependency_graph.rb +++ /dev/null @@ -1,244 +0,0 @@ -require 'set' - -module Bundler::Molinillo - # A directed acyclic graph that is tuned to hold named dependencies - class DependencyGraph - include Enumerable - - def each - vertices.values.each { |v| yield v } - 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 [Array] requirements The requirements the directed edge represents - Edge = Struct.new(:origin, :destination, :requirements) - - # @return [{String => Vertex}] vertices that have no {Vertex#predecessors}, - # keyed by by {Vertex#name} - attr_reader :root_vertices - # @return [{String => Vertex}] the vertices of the dependency graph, keyed - # by {Vertex#name} - attr_reader :vertices - # @return [Set] the edges of the dependency graph - attr_reader :edges - - def initialize - @vertices = {} - @edges = Set.new - @root_vertices = {} - end - - # Initializes a copy of a {DependencyGraph}, ensuring that all {#vertices} - # have the correct {Vertex#graph} set - def initialize_copy(other) - super - @vertices = other.vertices.reduce({}) do |vertices, (name, vertex)| - vertices.tap do |hash| - hash[name] = vertex.dup.tap { |v| v.graph = self } - end - end - @root_vertices = Hash[vertices.select { |n, _v| other.root_vertices[n] }] - @edges = other.edges.map do |edge| - Edge.new( - vertex_named(edge.origin.name), - vertex_named(edge.destination.name), - edge.requirements.dup - ) - end - end - - # @return [String] a string suitable for debugging - def inspect - "#{self.class}:#{vertices.values.inspect}" - end - - # @return [Boolean] whether the two dependency graphs are equal, determined - # by a recursive traversal of each {#root_vertices} and its - # {Vertex#successors} - def ==(other) - root_vertices == other.root_vertices - end - - # @param [String] name - # @param [Object] payload - # @param [Array] parent_names - # @param [Object] requirement the requirement that is requiring the child - # @return [void] - def add_child_vertex(name, payload, parent_names, requirement) - is_root = parent_names.include?(nil) - parent_nodes = parent_names.compact.map { |n| vertex_named(n) } - vertex = vertex_named(name) || if is_root - add_root_vertex(name, payload) - else - add_vertex(name, payload) - end - vertex.payload ||= payload - parent_nodes.each do |parent_node| - add_edge(parent_node, vertex, requirement) - end - vertex - end - - # @param [String] name - # @param [Object] payload - # @return [Vertex] the vertex that was added to `self` - def add_vertex(name, payload) - vertex = vertices[name] ||= Vertex.new(self, name, payload) - vertex.tap { |v| v.payload = payload } - end - - # @param [String] name - # @param [Object] payload - # @return [Vertex] the vertex that was added to `self` - def add_root_vertex(name, payload) - add_vertex(name, payload).tap { |v| root_vertices[name] = v } - 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 [void] - def detach_vertex_named(name) - vertex = vertex_named(name) - return unless vertex - successors = vertex.successors - vertices.delete(name) - edges.reject! { |e| e.origin == vertex || e.destination == vertex } - successors.each { |v| detach_vertex_named(v.name) unless root_vertices[v.name] || v.predecessors.any? } - 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) - root_vertices[name] - 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 origin == destination || destination.path_to?(origin) - raise CircularDependencyError.new([origin, destination]) - end - Edge.new(origin, destination, [requirement]).tap { |e| edges << e } - end - - # A vertex in a {DependencyGraph} that encapsulates a {#name} and a - # {#payload} - class Vertex - # @return [DependencyGraph] the graph this vertex is a node of - attr_accessor :graph - - # @return [String] the name of the vertex - attr_accessor :name - - # @return [Object] the payload the vertex holds - attr_accessor :payload - - # @return [Arrary] the explicit requirements that required - # this vertex - attr_reader :explicit_requirements - - # @param [DependencyGraph] graph see {#graph} - # @param [String] name see {#name} - # @param [Object] payload see {#payload} - def initialize(graph, name, payload) - @graph = graph - @name = name - @payload = payload - @explicit_requirements = [] - end - - # @return [Array] all of the requirements that required - # this vertex - def requirements - incoming_edges.flat_map(&:requirements) + explicit_requirements - end - - # @return [Array] the edges of {#graph} that have `self` as their - # {Edge#origin} - def outgoing_edges - graph.edges.select { |e| e.origin.shallow_eql?(self) } - end - - # @return [Array] the edges of {#graph} that have `self` as their - # {Edge#destination} - def incoming_edges - graph.edges.select { |e| e.destination.shallow_eql?(self) } - end - - # @return [Set] the vertices of {#graph} that have an edge with - # `self` as their {Edge#destination} - def predecessors - incoming_edges.map(&:origin).to_set - end - - # @return [Set] the vertices of {#graph} that have an edge with - # `self` as their {Edge#origin} - def successors - outgoing_edges.map(&:destination).to_set - end - - # @return [Set] the vertices of {#graph} where `self` is an - # {#ancestor?} - def recursive_successors - successors + successors.map(&:recursive_successors).reduce(Set.new, &:+) - end - - # @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) - shallow_eql?(other) && - successors == other.successors - end - - # @return [Boolean] whether the two vertices are equal, determined - # solely by {#name} and {#payload} equality - def shallow_eql?(other) - other && - name == other.name && - payload == other.payload - end - - alias_method :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 true iff there is a path following edges within this {#graph} - def path_to?(other) - successors.include?(other) || successors.any? { |v| v.path_to?(other) } - end - - alias_method :descendent?, :path_to? - - # Is there a path from `other` to `self` following edges in the - # dependency graph? - # @return true iff there is a path following edges within this {#graph} - def ancestor?(other) - predecessors.include?(other) || predecessors.any? { |v| v.ancestor?(other) } - end - - alias_method :is_reachable_from?, :ancestor? - end - end -end diff --git a/lib/bundler/vendor/Molinillo-master/lib/molinillo/errors.rb b/lib/bundler/vendor/Molinillo-master/lib/molinillo/errors.rb deleted file mode 100644 index b828d0c2..00000000 --- a/lib/bundler/vendor/Molinillo-master/lib/molinillo/errors.rb +++ /dev/null @@ -1,69 +0,0 @@ -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] the specifications that depended upon {#dependency} - attr_accessor :required_by - - # @param [Object] dependency @see {#dependency} - # @param [Array] required_by @see {#required_by} - def initialize(dependency, required_by = []) - @dependency = dependency - @required_by = required_by - super() - end - - 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 iff a {Vertex} is added to a - # {DependencyGraph} that has a {DependencyGraph::Vertex#path_to?} an - # existing {DependencyGraph::Vertex} - class CircularDependencyError < ResolverError - # [Set] the dependencies responsible for causing the error - attr_reader :dependencies - - # @param [Array] nodes the nodes in the dependency - # that caused the error - def initialize(nodes) - super "There is a circular dependency between #{nodes.map(&:name).join(' and ')}" - @dependencies = nodes.map(&:payload).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 - - # @param [{String => Resolution::Conflict}] conflicts see {#conflicts} - def initialize(conflicts) - pairs = [] - conflicts.values.flatten.map(&:requirements).flatten.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 - end - end -end diff --git a/lib/bundler/vendor/Molinillo-master/lib/molinillo/gem_metadata.rb b/lib/bundler/vendor/Molinillo-master/lib/molinillo/gem_metadata.rb deleted file mode 100644 index 7c5a03fa..00000000 --- a/lib/bundler/vendor/Molinillo-master/lib/molinillo/gem_metadata.rb +++ /dev/null @@ -1,3 +0,0 @@ -module Bundler::Molinillo - VERSION = '0.1.1' -end diff --git a/lib/bundler/vendor/Molinillo-master/lib/molinillo/modules/specification_provider.rb b/lib/bundler/vendor/Molinillo-master/lib/molinillo/modules/specification_provider.rb deleted file mode 100644 index 79a85e77..00000000 --- a/lib/bundler/vendor/Molinillo-master/lib/molinillo/modules/specification_provider.rb +++ /dev/null @@ -1,90 +0,0 @@ -module Bundler::Molinillo - # Provides information about specifcations 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] 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] 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 - - # 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] dependencies - # @param [DependencyGraph] activated the current dependency graph in the - # resolution process. - # @param [{String => Array}] conflicts - # @return [Array] 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 - end -end diff --git a/lib/bundler/vendor/Molinillo-master/lib/molinillo/modules/ui.rb b/lib/bundler/vendor/Molinillo-master/lib/molinillo/modules/ui.rb deleted file mode 100644 index fce3290d..00000000 --- a/lib/bundler/vendor/Molinillo-master/lib/molinillo/modules/ui.rb +++ /dev/null @@ -1,64 +0,0 @@ -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. - # By default, prints to `STDERR` instead of {#output}. - # - # @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) - STDERR.puts debug_info.split("\n").map { |s| ' ' * depth + s } - 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? - @debug_mode ||= ENV['MOLINILLO_DEBUG'] - end - end -end diff --git a/lib/bundler/vendor/Molinillo-master/lib/molinillo/resolution.rb b/lib/bundler/vendor/Molinillo-master/lib/molinillo/resolution.rb deleted file mode 100644 index a3f27253..00000000 --- a/lib/bundler/vendor/Molinillo-master/lib/molinillo/resolution.rb +++ /dev/null @@ -1,339 +0,0 @@ -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 the spec that was unable to be activated due - # to a conflict - Conflict = Struct.new( - :requirement, - :requirements, - :existing, - :possibility - ) - - # @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 - - # @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 - 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 unless state.requirements.any? || state.requirement - indicate_progress - if state.respond_to?(:pop_possibility_state) # DependencyState - debug(depth) { "Creating possibility state (#{possibilities.count} remaining)" } - state.pop_possibility_state.tap { |s| states.push(s) if s } - end - process_topmost_state - end - - activated.freeze - ensure - end_resolution - end - - private - - # Sets up the resolution process - # @return [void] - def start_resolution - @started_at = Time.now - - states.push(initial_state) - - debug { "Starting resolution (#{@started_at})" } - resolver_ui.before_resolution - 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 'molinillo/state' - require 'molinillo/modules/specification_provider' - - # @return [Integer] the number of resolver iterations in between calls to - # {#resolver_ui}'s {UI#indicate_progress} method - attr_accessor :iteration_rate - - # @return [Time] the time at which resolution began - attr_accessor :started_at - - # @return [Array] the stack of states for the resolution - attr_accessor :states - - ResolutionState.new.members.each do |member| - define_method member do |*args, &block| - state.send(member, *args, &block) - end - end - - SpecificationProvider.instance_methods(false).each do |instance_method| - define_method instance_method do |*args, &block| - begin - specification_provider.send(instance_method, *args, &block) - 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 - - # Processes the topmost available {RequirementState} on the stack - # @return [void] - def process_topmost_state - if possibility - attempt_to_activate - else - create_conflict if state.is_a? PossibilityState - unwind_for_conflict until possibility && state.is_a?(DependencyState) - end - 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 the initial state for the resolution, based upon the - # {#requested} dependencies - # @return [DependencyState] the initial state for the resolution - def initial_state - graph = DependencyGraph.new.tap do |dg| - original_requested.each { |r| dg.add_root_vertex(name_for(r), nil).tap { |v| v.explicit_requirements << r } } - end - - requirements = sort_dependencies(original_requested, graph, {}) - initial_requirement = requirements.shift - DependencyState.new( - initial_requirement && name_for(initial_requirement), - requirements, - graph, - initial_requirement, - initial_requirement && search_for(initial_requirement), - 0, - {} - ) - end - - # Unwinds the states stack because a conflict has been encountered - # @return [void] - def unwind_for_conflict - conflicts.tap do |c| - states.slice!(state_index_for_unwind..-1) - states.pop if state - raise VersionConflict.new(c) unless state - state.conflicts = c - end - end - - # @return [Integer] The index to which the resolution should unwind in the - # case of conflict. - def state_index_for_unwind - index = states.rindex do |state| - return nil unless vertex = state.activated.vertex_named(name) - state.is_a?(DependencyState) && - ( - !vertex.payload || - (!state.requirements.include?(requirement) && state.requirement != requirement) - ) - end - index + 2 - end - - # @return [Conflict] a {Conflict} that reflects the failure to activate - # the {#possibility} in conjunction with the current {#state} - def create_conflict - vertex = activated.vertex_named(name) - existing = vertex.payload - requirements = { - name_for_explicit_dependency_source => vertex.explicit_requirements, - name_for_locking_dependency_source => Array(locked_requirement_named(name)), - } - vertex.incoming_edges.each { |edge| (requirements[edge.origin.payload] ||= []).unshift(*edge.requirements) } - conflicts[name] = Conflict.new( - requirement, - Hash[requirements.select { |_, r| !r.empty? }], - existing, - possibility - ) - 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_node = activated.vertex_named(name) - if existing_node && existing_node.payload - attempt_to_activate_existing_spec(existing_node) - else - attempt_to_activate_new_spec - end - end - - # Attempts to activate the current {#possibility} (given that it has - # already been activated) - # @return [void] - def attempt_to_activate_existing_spec(existing_node) - existing_spec = existing_node.payload - if requirement_satisfied_by?(requirement, activated, existing_spec) - new_requirements = requirements.dup - push_state_for_requirements(new_requirements) - else - create_conflict - debug(depth) { 'Unsatisfied by existing spec' } - unwind_for_conflict - end - end - - # Attempts to activate the current {#possibility} (given that it hasn't - # already been activated) - # @return [void] - def attempt_to_activate_new_spec - satisfied = begin - locked_requirement = locked_requirement_named(name) - requested_spec_satisfied = requirement_satisfied_by?(requirement, activated, possibility) - locked_spec_satisfied = !locked_requirement || - requirement_satisfied_by?(locked_requirement, activated, possibility) - debug(depth) { 'Unsatisfied by requested spec' } unless requested_spec_satisfied - debug(depth) { 'Unsatisfied by locked spec' } unless locked_spec_satisfied - requested_spec_satisfied && locked_spec_satisfied - end - if satisfied - activate_spec - else - create_conflict - unwind_for_conflict - end - 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_spec - conflicts.delete(name) - debug(depth) { 'Activated ' + name + ' at ' + possibility.to_s } - vertex = activated.vertex_named(name) - vertex.payload = possibility - require_nested_dependencies_for(possibility) - end - - # Requires the dependencies that the recently activated spec has - # @param [Object] activated_spec the specification that has just been - # activated - # @return [void] - def require_nested_dependencies_for(activated_spec) - nested_dependencies = dependencies_for(activated_spec) - debug(depth) { "Requiring nested dependencies (#{nested_dependencies.map(&:to_s).join(', ')})" } - nested_dependencies.each { |d| activated.add_child_vertex name_for(d), nil, [name_for(activated_spec)], d } - - push_state_for_requirements(requirements + nested_dependencies) - end - - # Pushes a new {DependencyState} that encapsulates both existing and new - # requirements - # @param [Array] new_requirements - # @return [void] - def push_state_for_requirements(new_requirements) - new_requirements = sort_dependencies(new_requirements, activated, conflicts) - new_requirement = new_requirements.shift - states.push DependencyState.new( - new_requirement ? name_for(new_requirement) : '', - new_requirements, - activated.dup, - new_requirement, - new_requirement ? search_for(new_requirement) : [], - depth, - conflicts.dup - ) - end - end - end -end diff --git a/lib/bundler/vendor/Molinillo-master/lib/molinillo/resolver.rb b/lib/bundler/vendor/Molinillo-master/lib/molinillo/resolver.rb deleted file mode 100644 index 7cfe914d..00000000 --- a/lib/bundler/vendor/Molinillo-master/lib/molinillo/resolver.rb +++ /dev/null @@ -1,43 +0,0 @@ -require 'molinillo/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 the {#specification_provider} - # - # - class Resolver - require 'molinillo/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 - - # @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-master/lib/molinillo/state.rb b/lib/bundler/vendor/Molinillo-master/lib/molinillo/state.rb deleted file mode 100644 index 8e394f86..00000000 --- a/lib/bundler/vendor/Molinillo-master/lib/molinillo/state.rb +++ /dev/null @@ -1,43 +0,0 @@ -module Bundler::Molinillo - # A state that a {Resolution} can be in - # @attr [String] name - # @attr [Array] requirements - # @attr [DependencyGraph] activated - # @attr [Object] requirement - # @attr [Object] possibility - # @attr [Integer] depth - # @attr [Set] conflicts - ResolutionState = Struct.new( - :name, - :requirements, - :activated, - :requirement, - :possibilities, - :depth, - :conflicts - ) - - # 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.dup, - requirement, - [possibilities.pop], - depth + 1, - conflicts.dup - ) - end - end - - # A state that encapsulates a single possibility to fulfill the given - # {#requirement} - class PossibilityState < ResolutionState - end -end diff --git a/lib/bundler/vendored_molinillo.rb b/lib/bundler/vendored_molinillo.rb index f6c4a25a..daf52b82 100644 --- a/lib/bundler/vendored_molinillo.rb +++ b/lib/bundler/vendored_molinillo.rb @@ -1,4 +1,4 @@ -vendor = File.expand_path('../vendor/Molinillo-master/lib', __FILE__) +vendor = File.expand_path('../vendor/Molinillo-double-backjumping/lib', __FILE__) loaded = $:.include?(vendor) $:.unshift(vendor) unless loaded require 'molinillo' -- cgit v1.2.3