diff options
21 files changed, 1201 insertions, 414 deletions
diff --git a/CHANGELOG.md b/CHANGELOG.md index 974ecf9b..45538337 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -46,6 +46,7 @@ Features: - add `package --cache-path` and `config cache_path` for cache location (@jnraine) - allow `config` to work even when a Gemfile is not present (@dholdren) - add `config gemfile /path` for other Gemfile locations (@dholdren) + - add `github` method alonside the `git` method (@BenMorganIO) Bugfixes: @@ -27,6 +27,29 @@ module Rake end end +namespace :molinillo do + task :namespace do + files = Dir.glob('lib/bundler/vendor/Molinillo*/**/*.rb') + sh "sed -i.bak 's/Molinillo/Bundler::Molinillo/g' #{files.join(' ')}" + sh "rm #{files.join('.bak ')}.bak" + end + + task :clean do + files = Dir.glob('lib/bundler/vendor/Molinillo*/*', File::FNM_DOTMATCH).reject { |f| %(. .. lib).include? f.split('/').last } + puts files + sh "rm -r #{files.join(' ')}" + end + + task :update, [:tag] => [] do |t, args| + tag = args[:tag] + Dir.chdir 'lib/bundler/vendor' do + `curl -L https://github.com/CocoaPods/molinillo/archive/#{tag}.tar.gz | tar -xz` + end + Rake::Task['molinillo:namespace'].invoke + Rake::Task['molinillo:clean'].invoke + end +end + namespace :spec do desc "Ensure spec dependencies are installed" task :deps do diff --git a/lib/bundler/dep_proxy.rb b/lib/bundler/dep_proxy.rb index bc810dc5..ef98a351 100644 --- a/lib/bundler/dep_proxy.rb +++ b/lib/bundler/dep_proxy.rb @@ -1,10 +1,10 @@ module Bundler class DepProxy - attr_reader :required_by, :__platform, :dep + attr_reader :__platform, :dep def initialize(dep, platform) - @dep, @__platform, @required_by = dep, platform, [] + @dep, @__platform = dep, platform end def hash diff --git a/lib/bundler/resolver.rb b/lib/bundler/resolver.rb index 709ad67a..df2c515c 100644 --- a/lib/bundler/resolver.rb +++ b/lib/bundler/resolver.rb @@ -1,27 +1,73 @@ require 'set' + # This is the latest iteration of the gem dependency resolving algorithm. As of now, # it can resolve (as a success or failure) any set of gem dependencies we throw at it # in a reasonable amount of time. The most iterations I've seen it take is about 150. # The actual implementation of the algorithm is not as good as it could be yet, but that # can come later. -# Extending Gem classes to add necessary tracking information -module Gem - class Specification - def required_by - @required_by ||= [] - end - end - class Dependency - def required_by - @required_by ||= [] - end - end -end - module Bundler class Resolver + require 'bundler/vendored_molinillo' + + class Molinillo::VersionConflict + def clean_req(req) + if req.to_s.include?(">= 0") + req.to_s.gsub(/ \(.*?\)$/, '') + else + req.to_s.gsub(/\, (runtime|development)\)$/, ')') + end + end + + def message + conflicts.values.flatten.reduce('') do |o, conflict| + o << %(Bundler could not find compatible versions for gem "#{conflict.requirement.name}":\n) + if conflict.locked_requirement + o << %( In snapshot (Gemfile.lock):\n) + o << %( #{clean_req conflict.locked_requirement}\n) + o << %(\n) + end + o << %( In Gemfile:\n) + o << conflict.requirement_trees.map do |tree| + t = '' + depth = 2 + tree.each do |req| + t << ' ' * depth << %(#{clean_req req}) + t << %( depends on) unless tree[-1] == req + t << %(\n) + depth += 1 + end + t + end.join("\n") + + if conflict.requirement.name == 'bundler' + o << %(\n Current Bundler version:\n bundler (#{Bundler::VERSION})) + other_bundler_required = !conflict.requirement.requirement.satisfied_by?(Gem::Version.new Bundler::VERSION) + end + + if conflict.requirement.name == "bundler" && other_bundler_required + o << "\n" + o << "This Gemfile requires a different version of Bundler.\n" + o << "Perhaps you need to update Bundler by running `gem install bundler`?\n" + end + if conflict.locked_requirement + o << "\n" + o << %(Running `bundle update` will rebuild your snapshot from scratch, using only\n) + o << %(the gems in your Gemfile, which may resolve the conflict.\n) + elsif !conflict.existing + if conflict.requirement_trees.first.size > 1 + o << "Could not find gem '#{clean_req(conflict.requirement)}', which is required by " + o << "gem '#{clean_req(conflict.requirement_trees.first[-2])}', in any of the sources." + else + o << "Could not find gem '#{clean_req(conflict.requirement)} in any of the sources\n" + end + end + o + end + end + end + ALL = Bundler::Dependency::PLATFORM_MAP.values.uniq.freeze class SpecGroup < Array @@ -65,8 +111,10 @@ module Bundler def activate_platform(platform) unless @activated.include?(platform) - @activated << platform - return __dependencies[platform] || [] + if for?(platform) + @activated << platform + return __dependencies[platform] || [] + end end [] end @@ -91,6 +139,14 @@ module Bundler "#{name} (#{version})" end + def dependencies_for_activated_platforms + @activated.map { |p| __dependencies[p] }.flatten + end + + def platforms_for_dependency_named(dependency) + __dependencies.select { |p, deps| deps.map(&:name).include? dependency }.keys + end + private def __dependencies @@ -110,8 +166,6 @@ module Bundler end end - attr_reader :errors, :started_at, :iteration_rate, :iteration_counter, :initial_reqs - # Figures out the best possible configuration of gems that satisfies # the list of passed dependencies and any child dependencies without # causing any gem activation errors. @@ -123,289 +177,85 @@ module Bundler # <GemBundle>,nil:: If the list of dependencies can be resolved, a # collection of gemspecs is returned. Otherwise, nil is returned. def self.resolve(requirements, index, source_requirements = {}, base = []) - Bundler.ui.info "Resolving dependencies...", false base = SpecSet.new(base) unless base.is_a?(SpecSet) resolver = new(index, source_requirements, base) result = resolver.start(requirements) - Bundler.ui.info "" # new line now that dots are done SpecSet.new(result) - rescue => e - Bundler.ui.info "" # new line before the error - raise e - end - - def initialize(index, source_requirements, base) - @initial_reqs = [] - @errors = {} - @base = base - @index = index - @deps_for = {} - @missing_gems = Hash.new(0) - @prereleases_cache = Hash.new { |h,k| h[k] = k.prerelease? } - @source_requirements = source_requirements - @iteration_counter = 0 - @started_at = Time.now end - def debug - if ENV['DEBUG_RESOLVER'] - debug_info = yield - debug_info = debug_info.inspect unless debug_info.is_a?(String) - $stderr.puts debug_info - end - end - def successify(activated) - activated.values.map { |s| s.to_specs }.flatten.compact - end - - def start(reqs, current_traversal=false) - @initial_reqs = reqs.dup unless current_traversal - activated = {} - @gems_size = Hash[reqs.map { |r| [r, gems_size(r)] }] - - resolve(reqs, activated, current_traversal) + def initialize(index, source_requirements, base) + @index = index + @source_requirements = source_requirements + @base = base + @resolver = Molinillo::Resolver.new(self, self) + @search_for = {} + @prereleases_cache = Hash.new { |h,k| h[k] = k.prerelease? } + @base_dg = Molinillo::DependencyGraph.new + @base.each { |ls| @base_dg.add_root_vertex ls.name, Dependency.new(ls.name, ls.version) } end - class State < Struct.new(:reqs, :activated, :requirement, :possibles, :depth, :conflicts) - def name - requirement.name - end + def start(requirements) + verify_gemfile_dependencies_are_found!(requirements) + dg = @resolver.resolve(requirements, @base_dg) + dg.map(&:payload).map(&:to_specs).flatten + rescue Molinillo::VersionConflict => e + raise VersionConflict.new(e.conflicts.keys.uniq, e.message) + rescue Molinillo::CircularDependencyError => e + names = e.dependencies.sort_by(&:name).map { |d| "gem '#{d.name}'"} + raise CyclicDependencyError, "Your Gemfile requires gems that depend" \ + " on each other, creating an infinite loop. Please remove" \ + " #{names.count > 1 ? 'either ' : '' }#{names.join(' or ')}" \ + " and try again." end - def handle_conflict(current, states, existing=nil) - until current.nil? - current_state = find_state(current, states) - return current if state_any?(current_state) - current = current.required_by.last if current - end + include Molinillo::UI - until existing.nil? - existing_state = find_state(existing, states) - return existing if state_any?(existing_state) - existing = existing.required_by.last if existing + # Conveys debug information to the user. + # + # @param [Integer] depth the current depth of the resolution process. + # @return [void] + def debug(depth = 0) + if debug? + debug_info = yield + debug_info = debug_info.inspect unless debug_info.is_a?(String) + STDERR.puts debug_info.split("\n").map { |s| ' ' * depth + s } end end - def state_any?(state) - state && state.possibles.any? + def debug? + ENV['DEBUG_RESOLVER'] || ENV['DEBUG_RESOLVER_TREE'] end - def find_state(current, states) - states.detect { |i| current && current.name == i.name } + def before_resolution + Bundler.ui.info 'Resolving dependencies...', false end - def other_possible?(conflict, states) - return unless conflict - state = states.detect { |i| i.name == conflict.name } - state && state.possibles.any? + def after_resolution + Bundler.ui.info '' end - def find_conflict_state(conflict, states) - return unless conflict - until states.empty? do - state = states.pop - return state if conflict.name == state.name - end - end - - def activate_gem(reqs, activated, requirement, current) - requirement.required_by.replace current.required_by - requirement.required_by << current - activated[requirement.name] = requirement - - debug { " Activating: #{requirement.name} (#{requirement.version})" } - debug { requirement.required_by.map { |d| " * #{d.name} (#{d.requirement})" }.join("\n") } - - dependencies = requirement.activate_platform(current.__platform) - - debug { " Dependencies"} - dependencies.each do |dep| - next if dep.type == :development - dep.required_by.replace(current.required_by) - dep.required_by << current - @gems_size[dep] ||= gems_size(dep) - reqs << dep - end - end - - def resolve_for_conflict(state) - return version_conflict if state.nil? || state.possibles.empty? - reqs, activated, depth, conflicts = state.reqs.dup, state.activated.dup, state.depth, state.conflicts.dup - requirement = state.requirement - possible = state.possibles.pop - - activate_gem(reqs, activated, possible, requirement) - - return reqs, activated, depth, conflicts + def indicate_progress + Bundler.ui.info '.', false end - def resolve_conflict(current, states) - # Find the state where the conflict has occurred - state = find_conflict_state(current, states) - - debug { " -> Going to: #{current.name} state" } if current - - # Resolve the conflicts by rewinding the state - # when the conflicted gem was activated - reqs, activated, depth, conflicts = resolve_for_conflict(state) + private - # Keep the state around if it still has other possibilities - states << state unless state.possibles.empty? - clear_search_cache + include Molinillo::SpecificationProvider - return reqs, activated, depth, conflicts + def dependencies_for(specification) + specification.dependencies_for_activated_platforms end - def resolve(reqs, activated, current_traversal) - states = [] - depth = 0 - conflicts = Set.new - - until reqs.empty? - - indicate_progress - - debug { print "\e[2J\e[f" ; "==== Iterating ====\n\n" } - - reqs = reqs.sort_by do |a| - [ activated[a.name] ? 0 : 1, - @prereleases_cache[a.requirement] ? 0 : 1, - @errors[a.name] ? 0 : 1, - activated[a.name] ? 0 : @gems_size[a] ] - end - - debug { "Activated:\n" + activated.values.map {|a| " #{a}" }.join("\n") } - debug { "Requirements:\n" + reqs.map {|r| " #{r}"}.join("\n") } - - current = reqs.shift - - $stderr.puts "#{' ' * depth}#{current}" if ENV['DEBUG_RESOLVER_TREE'] - - debug { "Attempting:\n #{current}"} - - existing = activated[current.name] - - - if existing || current.name == 'bundler' - # Force the current - if current.name == 'bundler' && !existing - existing = search(DepProxy.new(Gem::Dependency.new('bundler', VERSION), Gem::Platform::RUBY)).first - raise GemNotFound, %Q{Bundler could not find gem "bundler" (#{VERSION})} unless existing - existing.required_by << existing - activated['bundler'] = existing - end - - if current.requirement.satisfied_by?(existing.version) - debug { " * [SUCCESS] Already activated" } - @errors.delete(existing.name) - dependencies = existing.activate_platform(current.__platform) - reqs.concat dependencies - - dependencies.each do |dep| - next if dep.type == :development - @gems_size[dep] ||= gems_size(dep) - end - - depth += 1 - next - else - debug { " * [FAIL] Already activated" } - @errors[existing.name] = [existing, current] - - conflicts << current.name - - parent = current.required_by.last - - if current_traversal - parent = handle_conflict(current, states) - else - parent = handle_conflict(parent, states) - end - - - if parent.nil? && !conflicts.empty? - parent = states.reverse.detect { |i| conflicts.include?(i.name) && state_any?(i)} - end - - if existing.respond_to?(:required_by) - parent = handle_conflict(parent, states, existing.required_by[-2]) unless other_possible?(parent, states) - end - - return version_conflict(current_traversal) if parent.nil? || parent.name == 'bundler' - - reqs, activated, depth, conflicts = resolve_conflict(parent, states) - end - else - matching_versions = search(current) - - # If we found no versions that match the current requirement - if matching_versions.empty? - # If this is a top-level Gemfile requirement - if current.required_by.empty? - if base = @base[current.name] and !base.empty? - version = base.first.version - message = "You have requested:\n" \ - " #{current.name} #{current.requirement}\n\n" \ - "The bundle currently has #{current.name} locked at #{version}.\n" \ - "Try running `bundle update #{current.name}`" - elsif current.source - name = current.name - versions = @source_requirements[name][name].map { |s| s.version } - message = "Could not find gem '#{current}' in #{current.source}.\n" - if versions.any? - message << "Source contains '#{name}' at: #{versions.join(', ')}" - else - message << "Source does not contain any versions of '#{current}'" - end - else - message = "Could not find gem '#{current}' " - if @index.source_types.include?(Bundler::Source::Rubygems) - message << "in any of the gem sources listed in your Gemfile." - else - message << "in the gems available on this machine." - end - end - raise GemNotFound, message - # This is not a top-level Gemfile requirement - else - @errors[current.name] = [nil, current] - parent = handle_conflict(current, states) - reqs, activated, depth = resolve_conflict(parent, states) - next - end - end - - - state = State.new(reqs.dup, activated.dup, current, matching_versions, depth, conflicts) - states << state - requirement = state.possibles.pop - activate_gem(reqs, activated, requirement, current) + def search_for(dependency) + platform = dependency.__platform + dependency = dependency.dep unless dependency.is_a? Gem::Dependency + search = @search_for[dependency] ||= begin + index = @source_requirements[dependency.name] || @index + results = index.search(dependency, @base[dependency.name]) + if vertex = @base_dg.vertex_named(dependency.name) + locked_requirement = vertex.payload.requirement end - end - successify(activated) - end - - def gems_size(dep) - search(dep).size - end - - def clear_search_cache - @deps_for = {} - end - - def search(dep) - if base = @base[dep.name] and base.any? - reqs = [dep.requirement.as_list, base.first.version.to_s].flatten.compact - d = Gem::Dependency.new(base.first.name, *reqs) - else - d = dep.dep - end - - @deps_for[d.hash] ||= begin - index = @source_requirements[d.name] || @index - results = index.search(d, @base[d.name]) - if results.any? version = results.first.version nested = [[]] @@ -416,139 +266,74 @@ module Bundler end nested.last << spec end - deps = nested.map{|a| SpecGroup.new(a) }.select{|sg| sg.for?(dep.__platform) } + groups = nested.map { |a| SpecGroup.new(a) } + !locked_requirement ? groups : groups.select { |sg| locked_requirement.satisfied_by? sg.version } else - deps = [] + [] end end + search.select { |sg| sg.for?(platform) }.each { |sg| sg.activate_platform(platform) } end - def clean_req(req) - if req.to_s.include?(">= 0") - req.to_s.gsub(/ \(.*?\)$/, '') - else - req.to_s.gsub(/\, (runtime|development)\)$/, ')') - end + def name_for(dependency) + dependency.name end - def version_conflict(current_traversal=true) - raise VersionConflict.new(errors.keys, error_message) if current_traversal - reset_state - start(initial_reqs, true) + def name_for_explicit_dependency_source + 'Gemfile' end - def reset_state - clear_search_cache - @errors = {} + def name_for_locking_dependency_source + 'Gemfile.lock' end - # For a given conflicted requirement, print out what exactly went wrong - def gem_message(requirement, required_by=[]) - m = "" - - # A requirement that is required by itself is actually in the Gemfile, and does - # not "depend on" itself - if requirement.required_by.first && requirement.required_by.first.name != requirement.name - dependency_tree(m, required_by) - m << "#{clean_req(requirement)}\n" - else - m << " #{clean_req(requirement)}\n" - end - m << "\n" + def requirement_satisfied_by?(requirement, activated, spec) + requirement.matches_spec?(spec) end - def dependency_tree(m, requirements) - requirements.each_with_index do |i, j| - m << " " << (" " * j) - m << "#{clean_req(i)}" - m << " depends on\n" + def sort_dependencies(dependencies, activated, conflicts) + dependencies.sort_by do |dependency| + name = name_for(dependency) + [ + activated.vertex_named(name).payload ? 0 : 1, + @prereleases_cache[dependency.requirement] ? 0 : 1, + conflicts[name] ? 0 : 1, + activated.vertex_named(name).payload ? 0 : search_for(dependency).count, + ] end - m << " " << (" " * requirements.size) end - def error_message - errors.inject("") do |o, (conflict, (origin, requirement))| - - # origin is the SpecSet of specs from the Gemfile that is conflicted with - if origin - - o << %{Bundler could not find compatible versions for gem "#{origin.name}":\n} - o << " In Gemfile:\n" - - required_by = requirement.required_by - o << gem_message(requirement, required_by) - - # If the origin is "bundler", the conflict is us - if origin.name == "bundler" - o << " Current Bundler version:\n" - other_bundler_required = !requirement.requirement.satisfied_by?(origin.version) - # If the origin is a LockfileParser, it does not respond_to :required_by - elsif !origin.respond_to?(:required_by) || !(origin.required_by.first) - o << " In snapshot (Gemfile.lock):\n" - end - - required_by = origin.required_by[0..-2] - o << gem_message(origin, required_by) - - # If the bundle wants a newer bundler than the running bundler, explain - if origin.name == "bundler" && other_bundler_required - o << "This Gemfile requires a different version of Bundler.\n" - o << "Perhaps you need to update Bundler by running `gem install bundler`?" - end - - # origin is nil if the required gem and version cannot be found in any of - # the specified sources - else - - # if the gem cannot be found because of a version conflict between lockfile and gemfile, - # print a useful error that suggests running `bundle update`, which may fix things - # - # @base is a SpecSet of the gems in the lockfile - # conflict is the name of the gem that could not be found - if locked = @base[conflict].first - o << "Bundler could not find compatible versions for gem #{conflict.inspect}:\n" - o << " In snapshot (Gemfile.lock):\n" - o << " #{clean_req(locked)}\n\n" - - o << " In Gemfile:\n" - - required_by = requirement.required_by - o << gem_message(requirement, required_by) - o << "Running `bundle update` will rebuild your snapshot from scratch, using only\n" - o << "the gems in your Gemfile, which may resolve the conflict.\n" - - # the rest of the time, the gem cannot be found because it does not exist in the known sources + def verify_gemfile_dependencies_are_found!(requirements) + requirements.each do |requirement| + next if requirement.name == 'bundler' + if search_for(requirement).empty? + if base = @base[requirement.name] and !base.empty? + version = base.first.version + message = "You have requested:\n" \ + " #{requirement.name} #{requirement.requirement}\n\n" \ + "The bundle currently has #{requirement.name} locked at #{version}.\n" \ + "Try running `bundle update #{requirement.name}`" + elsif requirement.source + name = requirement.name + versions = @source_requirements[name][name].map { |s| s.version } + message = "Could not find gem '#{requirement}' in #{requirement.source}.\n" + if versions.any? + message << "Source contains '#{name}' at: #{versions.join(', ')}" + else + message << "Source does not contain any versions of '#{requirement}'" + end else - if requirement.required_by.first - o << "Could not find gem '#{clean_req(requirement)}', which is required by " - o << "gem '#{clean_req(requirement.required_by.first)}', in any of the sources." + message = "Could not find gem '#{requirement}' " + if @index.source_types.include?(Bundler::Source::Rubygems) + message << "in any of the gem sources listed in your Gemfile." else - o << "Could not find gem '#{clean_req(requirement)} in any of the sources\n" + message << "in the gems available on this machine." end end - + raise GemNotFound, message end - o end end - private - - # Indicates progress by writing a '.' every iteration_rate time which is - # approximately every second. iteration_rate is calculated in the first - # second of resolve running. - def indicate_progress - @iteration_counter += 1 - - if iteration_rate.nil? - if ((Time.now - started_at) % 3600).round >= 1 - @iteration_rate = iteration_counter - end - else - if ((iteration_counter % iteration_rate) == 0) - Bundler.ui.info ".", false - end - end - end end end diff --git a/lib/bundler/vendor/Molinillo-seg-bundler/lib/molinillo.rb b/lib/bundler/vendor/Molinillo-seg-bundler/lib/molinillo.rb new file mode 100644 index 00000000..bf740e48 --- /dev/null +++ b/lib/bundler/vendor/Molinillo-seg-bundler/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-seg-bundler/lib/molinillo/dependency_graph.rb b/lib/bundler/vendor/Molinillo-seg-bundler/lib/molinillo/dependency_graph.rb new file mode 100644 index 00000000..4ee5708a --- /dev/null +++ b/lib/bundler/vendor/Molinillo-seg-bundler/lib/molinillo/dependency_graph.rb @@ -0,0 +1,266 @@ +require 'set' +require 'tsort' + +module Bundler::Molinillo + # A directed acyclic graph that is tuned to hold named dependencies + class DependencyGraph + include Enumerable + + # Enumerates through the vertices of the graph. + # @return [Array<Vertex>] The graph's vertices. + def each + vertices.values.each { |v| yield v } + end + + include TSort + + alias_method :tsort_each_node, :each + + def tsort_each_child(vertex, &block) + vertex.successors.each(&block) + end + + # Topologically sorts the given vertices. + # @param [Enumerable<Vertex>] vertices the vertices to be sorted, which must + # all belong to the same graph. + # @return [Array<Vertex>] The sorted vertices. + def self.tsort(vertices) + TSort.tsort( + lambda { |b| vertices.each(&b) }, + lambda { |v, &b| (v.successors & vertices).each(&b) } + ) + end + + # A directed edge of a {DependencyGraph} + # @attr [Vertex] origin The origin of the directed edge + # @attr [Vertex] destination The destination of the directed edge + # @attr [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<Edge>] 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<String>] 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<Object>] 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<Object>] all of the requirements that required + # this vertex + def requirements + incoming_edges.map(&:requirements).flatten + explicit_requirements + end + + # @return [Array<Edge>] 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<Edge>] 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<Vertex>] 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<Vertex>] 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<Vertex>] 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-seg-bundler/lib/molinillo/errors.rb b/lib/bundler/vendor/Molinillo-seg-bundler/lib/molinillo/errors.rb new file mode 100644 index 00000000..b828d0c2 --- /dev/null +++ b/lib/bundler/vendor/Molinillo-seg-bundler/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<Object>] the specifications that depended upon {#dependency} + attr_accessor :required_by + + # @param [Object] dependency @see {#dependency} + # @param [Array<Object>] 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<Object>] the dependencies responsible for causing the error + attr_reader :dependencies + + # @param [Array<DependencyGraph::Vertex>] 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-seg-bundler/lib/molinillo/gem_metadata.rb b/lib/bundler/vendor/Molinillo-seg-bundler/lib/molinillo/gem_metadata.rb new file mode 100644 index 00000000..880ea9b6 --- /dev/null +++ b/lib/bundler/vendor/Molinillo-seg-bundler/lib/molinillo/gem_metadata.rb @@ -0,0 +1,3 @@ +module Bundler::Molinillo + VERSION = '0.2.0' +end diff --git a/lib/bundler/vendor/Molinillo-seg-bundler/lib/molinillo/modules/specification_provider.rb b/lib/bundler/vendor/Molinillo-seg-bundler/lib/molinillo/modules/specification_provider.rb new file mode 100644 index 00000000..79a85e77 --- /dev/null +++ b/lib/bundler/vendor/Molinillo-seg-bundler/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<Object>] the specifications that satisfy the given + # `dependency`. + def search_for(dependency) + [] + end + + # Returns the dependencies of `specification`. + # @note This method should be 'pure', i.e. the return value should depend + # only on the `specification` parameter. + # + # @param [Object] specification + # @return [Array<Object>] the dependencies that are required by the given + # `specification`. + def dependencies_for(specification) + [] + end + + # Determines whether the given `requirement` is satisfied by the given + # `spec`, in the context of the current `activated` dependency graph. + # + # @param [Object] requirement + # @param [DependencyGraph] activated the current dependency graph in the + # resolution process. + # @param [Object] spec + # @return [Boolean] whether `requirement` is satisfied by `spec` in the + # context of the current `activated` dependency graph. + def requirement_satisfied_by?(requirement, activated, spec) + true + end + + # Returns the name for the given `dependency`. + # @note This method should be 'pure', i.e. the return value should depend + # only on the `dependency` parameter. + # + # @param [Object] dependency + # @return [String] the name for the given `dependency`. + def name_for(dependency) + dependency.to_s + end + + # @return [String] the name of the source of explicit dependencies, i.e. + # those passed to {Resolver#resolve} directly. + def name_for_explicit_dependency_source + 'user-specified dependency' + end + + # @return [String] the name of the source of 'locked' dependencies, i.e. + # those passed to {Resolver#resolve} directly as the `base` + def name_for_locking_dependency_source + 'Lockfile' + end + + # Sort dependencies so that the ones that are easiest to resolve are first. + # Easiest to resolve is (usually) defined by: + # 1) Is this dependency already activated? + # 2) How relaxed are the requirements? + # 3) Are there any conflicts for this dependency? + # 4) How many possibilities are there to satisfy this dependency? + # + # @param [Array<Object>] dependencies + # @param [DependencyGraph] activated the current dependency graph in the + # resolution process. + # @param [{String => Array<Conflict>}] conflicts + # @return [Array<Object>] a sorted copy of `dependencies`. + def sort_dependencies(dependencies, activated, conflicts) + dependencies.sort_by do |dependency| + name = name_for(dependency) + [ + activated.vertex_named(name).payload ? 0 : 1, + conflicts[name] ? 0 : 1, + ] + end + end + end +end diff --git a/lib/bundler/vendor/Molinillo-seg-bundler/lib/molinillo/modules/ui.rb b/lib/bundler/vendor/Molinillo-seg-bundler/lib/molinillo/modules/ui.rb new file mode 100644 index 00000000..097c0264 --- /dev/null +++ b/lib/bundler/vendor/Molinillo-seg-bundler/lib/molinillo/modules/ui.rb @@ -0,0 +1,63 @@ +module Bundler::Molinillo + # Conveys information about the resolution process to a user. + module UI + # The {IO} object that should be used to print output. `STDOUT`, by default. + # + # @return [IO] + def output + STDOUT + end + + # Called roughly every {#progress_rate}, this method should convey progress + # to the user. + # + # @return [void] + def indicate_progress + output.print '.' unless debug? + end + + # How often progress should be conveyed to the user via + # {#indicate_progress}, in seconds. A third of a second, by default. + # + # @return [Float] + def progress_rate + 0.33 + end + + # Called before resolution begins. + # + # @return [void] + def before_resolution + output.print 'Resolving dependencies...' + end + + # Called after resolution ends (either successfully or with an error). + # By default, prints a newline. + # + # @return [void] + def after_resolution + output.puts + end + + # Conveys debug information to the user. + # + # @param [Integer] depth the current depth of the resolution process. + # @return [void] + def debug(depth = 0) + if debug? + debug_info = yield + debug_info = debug_info.inspect unless debug_info.is_a?(String) + output.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-seg-bundler/lib/molinillo/resolution.rb b/lib/bundler/vendor/Molinillo-seg-bundler/lib/molinillo/resolution.rb new file mode 100644 index 00000000..376e4d4e --- /dev/null +++ b/lib/bundler/vendor/Molinillo-seg-bundler/lib/molinillo/resolution.rb @@ -0,0 +1,412 @@ +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<Array<Object>>] 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 + 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 + + 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<ResolutionState>] 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 + 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? + current_state = find_state_for(current_requirement) + return states.index(current_state) if state_any?(current_state) + current_requirement = parent_of(current_requirement) + end + + until existing_requirement.nil? + existing_state = find_state_for(existing_requirement) + return states.index(existing_state) if state_any?(existing_state) + existing_requirement = parent_of(existing_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.reverse_each.find { |i| requirement == i.requirement && i.is_a?(DependencyState) } + end + + # @return [Boolean] whether or not the given state has any possibilities + # left. + def state_any?(state) + state && state.possibilities.any? + 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) } + conflicts[name] = Conflict.new( + requirement, + Hash[requirements.select { |_, r| !r.empty? }], + vertex.payload, + possibility, + locked_requirement_named(name), + requirement_trees + ) + end + + # @return [Array<Array<Object>>] The 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<Object>] the list of requirements that led to + # `requirement` being required. + def requirement_tree_for(requirement) + tree = [] + while requirement + tree.unshift(requirement) + requirement = parent_of(requirement) + end + tree + end + + # Indicates progress roughly once every second + # @return [void] + def indicate_progress + @iteration_counter += 1 + @progress_rate ||= resolver_ui.progress_rate + if iteration_rate.nil? + if Time.now - started_at >= @progress_rate + self.iteration_rate = @iteration_counter + end + end + + if iteration_rate && (@iteration_counter % iteration_rate) == 0 + resolver_ui.indicate_progress + end + end + + # Calls the {#resolver_ui}'s {UI#debug} method + # @param [Integer] depth the depth of the {#states} stack + # @param [Proc] block a block that yields a {#to_s} + # @return [void] + def debug(depth = 0, &block) + resolver_ui.debug(depth, &block) + end + + # Attempts to activate the current {#possibility} + # @return [void] + def attempt_to_activate + debug(depth) { 'Attempting to activate ' + possibility.to_s } + existing_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 + return if attempt_to_swap_possibility + create_conflict + debug(depth) { "Unsatisfied by existing spec (#{existing_node.payload})" } + unwind_for_conflict + end + end + + # Attempts to swp the current {#possibility} with the already-activated + # spec with the given name + # @return [Boolean] Whether the possibility was swapped into {#activated} + def attempt_to_swap_possibility + swapped = activated.dup + swapped.vertex_named(name).payload = possibility + return unless swapped.vertex_named(name).requirements. + all? { |r| requirement_satisfied_by?(r, swapped, possibility) } + attempt_to_activate_new_spec + 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.uniq, 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-seg-bundler/lib/molinillo/resolver.rb b/lib/bundler/vendor/Molinillo-seg-bundler/lib/molinillo/resolver.rb new file mode 100644 index 00000000..7cfe914d --- /dev/null +++ b/lib/bundler/vendor/Molinillo-seg-bundler/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-seg-bundler/lib/molinillo/state.rb b/lib/bundler/vendor/Molinillo-seg-bundler/lib/molinillo/state.rb new file mode 100644 index 00000000..8e394f86 --- /dev/null +++ b/lib/bundler/vendor/Molinillo-seg-bundler/lib/molinillo/state.rb @@ -0,0 +1,43 @@ +module Bundler::Molinillo + # A state that a {Resolution} can be in + # @attr [String] name + # @attr [Array<Object>] requirements + # @attr [DependencyGraph] activated + # @attr [Object] requirement + # @attr [Object] possibility + # @attr [Integer] depth + # @attr [Set<Object>] 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 new file mode 100644 index 00000000..5e1a4256 --- /dev/null +++ b/lib/bundler/vendored_molinillo.rb @@ -0,0 +1,5 @@ +vendor = File.expand_path('../vendor/Molinillo-seg-bundler/lib', __FILE__) +loaded = $:.include?(vendor) +$:.unshift(vendor) unless loaded +require 'molinillo' +$:.delete(vendor) unless loaded diff --git a/lib/bundler/version.rb b/lib/bundler/version.rb index c0cb4c86..73d9219c 100644 --- a/lib/bundler/version.rb +++ b/lib/bundler/version.rb @@ -2,5 +2,5 @@ module Bundler # We're doing this because we might write tests that deal # with other versions of bundler and we are unsure how to # handle this better. - VERSION = "1.8.0" unless defined?(::Bundler::VERSION) + VERSION = "1.9.0.dev" unless defined?(::Bundler::VERSION) end diff --git a/spec/install/bundler_spec.rb b/spec/install/bundler_spec.rb index b85ddf8c..066b9309 100644 --- a/spec/install/bundler_spec.rb +++ b/spec/install/bundler_spec.rb @@ -104,7 +104,7 @@ describe "bundle install" do activesupport (>= 2.0.0) ruby rails_fail (>= 0) ruby depends on - activesupport (1.2.3) + activesupport (= 1.2.3) ruby E expect(out).to eq(nice_error) end @@ -124,7 +124,7 @@ describe "bundle install" do rails_fail (>= 0) ruby depends on activesupport (= 1.2.3) ruby - activesupport (2.3.5) + activesupport (= 2.3.5) ruby E expect(out).to eq(nice_error) end diff --git a/spec/install/gems/flex_spec.rb b/spec/install/gems/flex_spec.rb index dbf9278a..691a6a86 100644 --- a/spec/install/gems/flex_spec.rb +++ b/spec/install/gems/flex_spec.rb @@ -197,7 +197,7 @@ describe "bundle flex_install" do Resolving dependencies... Bundler could not find compatible versions for gem "rack": In snapshot (Gemfile.lock): - rack (0.9.1) + rack (= 0.9.1) In Gemfile: rack-obama (= 2.0) ruby depends on diff --git a/spec/install/gems/resolving_spec.rb b/spec/install/gems/resolving_spec.rb index 6e07073b..ef8aecf1 100644 --- a/spec/install/gems/resolving_spec.rb +++ b/spec/install/gems/resolving_spec.rb @@ -80,7 +80,7 @@ describe "bundle install with gem sources" do bundle :install, :env => {"DEBUG_RESOLVER" => "1"} end - expect(resolve_output).to include("==== Iterating ====") + expect(resolve_output).to include("Creating possibility state for net_c") end end diff --git a/spec/quality_spec.rb b/spec/quality_spec.rb index 0a388705..378f62d3 100644 --- a/spec/quality_spec.rb +++ b/spec/quality_spec.rb @@ -96,7 +96,7 @@ describe "The library itself" do end end - expect(@err).to eq("") + expect(@err.split("\n").reject { |f| f =~ %r{lib/bundler/vendor} }).to eq([]) expect(@out).to eq("") end end diff --git a/spec/realworld/parallel_spec.rb b/spec/realworld/parallel_spec.rb index 5fc3dd1e..ef370205 100644 --- a/spec/realworld/parallel_spec.rb +++ b/spec/realworld/parallel_spec.rb @@ -22,26 +22,6 @@ describe "parallel", :realworld => true do expect(out).to match(/: "4"/) end - it "installs even with circular dependency", :ruby => "1.9" do - gemfile <<-G - source 'https://rubygems.org' - gem 'activesupport', '~> 3.2.13' - gem 'mongoid_auto_increment', "0.1.1" - G - - bundle :install, :jobs => 4, :env => {"DEBUG" => "1"} - expect(out).to match(/[1-3]: /) - - bundle "show activesupport" - expect(out).to match(/activesupport/) - - bundle "show mongoid_auto_increment" - expect(out).to match(%r{gems/mongoid_auto_increment}) - - bundle "config jobs" - expect(out).to match(/: "4"/) - end - it "updates" do install_gemfile <<-G source "https://rubygems.org" diff --git a/spec/resolver/basic_spec.rb b/spec/resolver/basic_spec.rb index e588c9ec..12458985 100644 --- a/spec/resolver/basic_spec.rb +++ b/spec/resolver/basic_spec.rb @@ -57,10 +57,9 @@ describe "Resolving" do @index = a_circular_index dep "circular_app" - got = resolve expect { - got = got.map { |s| s.full_name }.sort - }.to raise_error(Bundler::CyclicDependencyError, /please remove either gem 'foo' or gem 'bar'/i) + resolve + }.to raise_error(Bundler::CyclicDependencyError, /please remove either gem 'bar' or gem 'foo'/i) end end |