summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--lib/bundler/finder.rb2
-rw-r--r--lib/bundler/manifest.rb2
-rw-r--r--lib/bundler/resolver.rb48
-rw-r--r--lib/bundler/resolver/builders.rb61
-rw-r--r--lib/bundler/resolver/engine.rb40
-rw-r--r--lib/bundler/resolver/inspect.rb24
-rw-r--r--lib/bundler/resolver/search.rb71
-rw-r--r--lib/bundler/resolver/stack.rb72
-rw-r--r--lib/bundler/resolver/state.rb172
-rw-r--r--spec/builders.rb59
-rw-r--r--spec/resolver/engine_spec.rb10
-rw-r--r--spec/spec_helper.rb4
12 files changed, 103 insertions, 462 deletions
diff --git a/lib/bundler/finder.rb b/lib/bundler/finder.rb
index bc4711387e..ab9d95146e 100644
--- a/lib/bundler/finder.rb
+++ b/lib/bundler/finder.rb
@@ -33,7 +33,7 @@ module Bundler
Bundler.logger.info "Calculating dependencies..."
resolved = Resolver.resolve(dependencies, self)
- resolved && GemBundle.new(resolved.all_specs)
+ resolved && GemBundle.new(resolved)
end
# Fetches the index from the remote source
diff --git a/lib/bundler/manifest.rb b/lib/bundler/manifest.rb
index 31d69f8ae1..7d765ac31e 100644
--- a/lib/bundler/manifest.rb
+++ b/lib/bundler/manifest.rb
@@ -39,7 +39,7 @@ module Bundler
deps = deps.select { |d| d.in?(environment) } if environment
deps = deps.map { |d| d.to_gem_dependency }
index = Gem::SourceIndex.from_gems_in(@gem_path.join("specifications"))
- Resolver.resolve(deps, index).all_specs
+ Resolver.resolve(deps, index)
end
alias gems gems_for
diff --git a/lib/bundler/resolver.rb b/lib/bundler/resolver.rb
index 1ec89e53c4..1b0c0ce98d 100644
--- a/lib/bundler/resolver.rb
+++ b/lib/bundler/resolver.rb
@@ -1,19 +1,41 @@
-require 'bundler/resolver/inspect'
-require 'bundler/resolver/search'
-require 'bundler/resolver/engine'
-require 'bundler/resolver/stack'
-require 'bundler/resolver/state'
-
module Bundler
- module Resolver
- def self.resolve(deps, source_index = Gem.source_index, logger = nil)
- unless logger
- logger = Logger.new($stderr)
- logger.datetime_format = ""
- logger.level = ENV["GEM_RESOLVER_DEBUG"] ? Logger::DEBUG : Logger::ERROR
+
+ class Resolver
+ def self.resolve(requirements, index = Gem.source_index)
+ result = catch(:success) do
+ new(index).resolve(requirements, {})
end
+ result && result.values
+ end
+
+ def initialize(index)
+ @index = index
+ end
+
+ def resolve(reqs, activated)
+ return activated if reqs.empty?
- Engine.resolve(deps, source_index, logger)
+ reqs = reqs.sort_by {|dep| @index.search(dep).size }
+ activated = activated.dup
+ current = reqs.shift
+
+ if existing = activated[current.name]
+ if current.version_requirements.satisfied_by?(existing.version)
+ resolve(reqs, activated)
+ end
+ else
+ specs = @index.search(current)
+ specs.reverse!
+ specs.each do |spec|
+ activated[spec.name] = spec
+ new_reqs = reqs + spec.dependencies.select do |d|
+ d.type != :development
+ end
+ retval = resolve(new_reqs, activated)
+ throw :success, retval if retval
+ end
+ nil
+ end
end
end
end \ No newline at end of file
diff --git a/lib/bundler/resolver/builders.rb b/lib/bundler/resolver/builders.rb
deleted file mode 100644
index 2b7b48211c..0000000000
--- a/lib/bundler/resolver/builders.rb
+++ /dev/null
@@ -1,61 +0,0 @@
-module Bundler
- module Resolver
- module Builders
- def build_index(&block)
- index = Gem::SourceIndex.new
- IndexBuilder.run(index, &block) if block_given?
- index
- end
-
- def build_spec(name, version, &block)
- spec = Gem::Specification.new
- spec.instance_variable_set(:@name, name)
- spec.instance_variable_set(:@version, Gem::Version.new(version))
- DepBuilder.run(spec, &block) if block_given?
- spec
- end
-
- def build_dep(name, requirements, type = :runtime)
- Gem::Dependency.new(name, requirements, type)
- end
-
- class IndexBuilder
- include Builders
-
- def self.run(index, &block)
- new(index).run(&block)
- end
-
- def initialize(index)
- @index = index
- end
-
- def run(&block)
- instance_eval(&block)
- end
-
- def add_spec(*args, &block)
- @index.add_spec(build_spec(*args, &block))
- end
- end
-
- class DepBuilder
- def self.run(spec, &block)
- new(spec).run(&block)
- end
-
- def initialize(spec)
- @spec = spec
- end
-
- def run(&block)
- instance_eval(&block)
- end
-
- def runtime(name, requirements)
- @spec.add_runtime_dependency(name, requirements)
- end
- end
- end
- end
-end \ No newline at end of file
diff --git a/lib/bundler/resolver/engine.rb b/lib/bundler/resolver/engine.rb
deleted file mode 100644
index 6412aefca8..0000000000
--- a/lib/bundler/resolver/engine.rb
+++ /dev/null
@@ -1,40 +0,0 @@
-module Bundler
- module Resolver
- class ClosedSet < Set
- end
-
- class Engine
- include Search, Inspect
-
- def self.resolve(deps, source_index, logger)
- new(deps, source_index, logger).resolve
- end
-
- def initialize(deps, source_index, logger)
- @deps, @source_index, @logger = deps, source_index, logger
- logger.debug "searching for #{gem_resolver_inspect(@deps)}"
- end
- attr_reader :deps, :source_index, :logger, :solution
-
- def resolve
- @deps = @deps.sort_by { |dep| @source_index.search(dep).size }
-
- state = State.initial(self, [], Stack.new, Stack.new([[[], @deps.dup]]))
- if solution = search(state)
- logger.info "got the solution with #{solution.all_specs.size} specs"
- solution.dump(Logger::INFO)
- solution
- end
- end
-
- def open
- @open ||= []
- end
-
- def closed
- @closed ||= ClosedSet.new
- end
- end
- end
-
-end \ No newline at end of file
diff --git a/lib/bundler/resolver/inspect.rb b/lib/bundler/resolver/inspect.rb
deleted file mode 100644
index 59640aa5f3..0000000000
--- a/lib/bundler/resolver/inspect.rb
+++ /dev/null
@@ -1,24 +0,0 @@
-module Bundler
- module Resolver
- module Inspect
- def gem_resolver_inspect(o)
- case o
- when Gem::Specification
- "#<Spec: #{o.full_name}>"
- when Array
- '[' + o.map {|x| gem_resolver_inspect(x)}.join(", ") + ']'
- when Set
- gem_resolver_inspect(o.to_a)
- when Hash
- '{' + o.map {|k,v| "#{gem_resolver_inspect(k)} => #{gem_resolver_inspect(v)}"}.join(", ") + '}'
- when Stack
- o.gem_resolver_inspect
- else
- o.inspect
- end
- end
-
- module_function :gem_resolver_inspect
- end
- end
-end \ No newline at end of file
diff --git a/lib/bundler/resolver/search.rb b/lib/bundler/resolver/search.rb
deleted file mode 100644
index 34102ff04c..0000000000
--- a/lib/bundler/resolver/search.rb
+++ /dev/null
@@ -1,71 +0,0 @@
-module Bundler
- module Resolver
- module Search
- def search(initial, max_depth = (1.0 / 0.0))
- if initial.goal_met?
- return initial
- end
-
- open << initial
-
- while open.any?
- current = open.pop
- closed << current
-
- new = []
- current.each_possibility do |attempt|
- unless closed.include?(attempt)
- if attempt.goal_met?
- return attempt
- elsif attempt.depth < max_depth
- new << attempt
- end
- end
- end
- new.reverse.each do |state|
- open << state
- end
- end
-
- nil
- end
-
- def open
- raise "implement #open in #{self.class}"
- end
-
- def closed
- raise "implement #closed in #{self.class}"
- end
-
- module Node
- def self.included(base)
- base.extend(ClassMethods)
- end
-
- module ClassMethods
- def initial(*data)
- new(0, *data)
- end
- end
-
- def initialize(depth)
- @depth = depth
- end
- attr_reader :depth
-
- def child(*data)
- self.class.new(@depth + 1, *data)
- end
-
- def each_possibility
- raise "implement #each_possibility on #{self.class}"
- end
-
- def goal_met?
- raise "implement #goal_met? on #{self.class}"
- end
- end
- end
- end
-end \ No newline at end of file
diff --git a/lib/bundler/resolver/stack.rb b/lib/bundler/resolver/stack.rb
deleted file mode 100644
index 6e1ac67e1f..0000000000
--- a/lib/bundler/resolver/stack.rb
+++ /dev/null
@@ -1,72 +0,0 @@
-module Bundler
- module Resolver
- class Stack
- def initialize(initial = [])
- @data = []
- initial.each do |(path,value)|
- self[path] = value
- end
- end
-
- def last
- @data.last
- end
-
- def []=(path, value)
- raise ArgumentError, "#{path.inspect} already has a value" if key?(path)
- @data << [path.dup, value]
- end
-
- def [](path)
- if key?(path)
- _, value = @data.find do |(k,v)|
- k == path
- end
- value
- else
- raise "No value for #{path.inspect}"
- end
- end
-
- def key?(path)
- @data.any? do |(k,v)|
- k == path
- end
- end
-
- def each
- @data.each do |(k,v)|
- yield k, v
- end
- end
-
- def map
- @data.map do |(k,v)|
- yield k, v
- end
- end
-
- def each_value
- @data.each do |(k,v)|
- yield v
- end
- end
-
- def dup
- self.class.new(@data.dup)
- end
-
- def to_s
- @data.to_s
- end
-
- def inspect
- @data.inspect
- end
-
- def gem_resolver_inspect
- Inspect.gem_resolver_inspect(@data)
- end
- end
- end
-end \ No newline at end of file
diff --git a/lib/bundler/resolver/state.rb b/lib/bundler/resolver/state.rb
deleted file mode 100644
index f13ecbbee7..0000000000
--- a/lib/bundler/resolver/state.rb
+++ /dev/null
@@ -1,172 +0,0 @@
-module Bundler
- module Resolver
- class State
- include Search::Node, Inspect
-
- def initialize(depth, engine, path, spec_stack, dep_stack)
- super(depth)
- @engine, @path, @spec_stack, @dep_stack = engine, path, spec_stack, dep_stack
- end
- attr_reader :path
-
- def logger
- @engine.logger
- end
-
- def goal_met?
- logger.info "checking if goal is met"
- dump
- no_duplicates?
- all_deps.all? do |dep|
- dependency_satisfied?(dep)
- end
- end
-
- def no_duplicates?
- names = []
- all_specs.each do |s|
- if names.include?(s.name)
- raise "somehow got duplicates for #{s.name}"
- end
- names << s.name
- end
- end
-
- def dependency_satisfied?(dep)
- all_specs.any? do |spec|
- spec.satisfies_requirement?(dep)
- end
- end
-
- def each_possibility(&block)
- index, dep = remaining_deps.first
- if dep
- logger.warn "working on #{dep} for #{spec_name}"
- handle_dep(index, dep, &block)
- else
- logger.warn "no dependencies left for #{spec_name}"
- jump_to_parent(&block)
- end
- end
-
- def handle_dep(index, dep)
- specs = @engine.source_index.search(dep)
-
- specs.reverse.each do |s|
- logger.info "attempting with spec: #{s.full_name}"
- new_path = @path + [index]
- new_spec_stack = @spec_stack.dup
- new_dep_stack = @dep_stack.dup
-
- new_spec_stack[new_path] = s
- new_dep_stack[new_path] = s.runtime_dependencies.sort_by do |dep|
- @engine.source_index.search(dep).size
- end
- yield child(@engine, new_path, new_spec_stack, new_dep_stack)
- end
- end
-
- def jump_to_parent
- if @path.empty?
- dump
- logger.warn "at the end"
- return
- end
-
- logger.info "jumping to parent for #{spec_name}"
- new_path = @path[0..-2]
- new_spec_stack = @spec_stack.dup
- new_dep_stack = @dep_stack.dup
-
- yield child(@engine, new_path, new_spec_stack, new_dep_stack)
- end
-
- def remaining_deps
- remaining_deps_for(@path)
- end
-
- def remaining_deps_for(path)
- no_duplicates?
- remaining = []
- @dep_stack[path].each_with_index do |dep,i|
- remaining << [i, dep] unless all_specs.find {|s| s.name == dep.name}
- end
- remaining
- end
-
- def deps
- @dep_stack[@path]
- end
-
- def spec
- @spec_stack[@path]
- end
-
- def spec_name
- @path.empty? ? "<top>" : spec.full_name
- end
-
- def all_deps
- all_deps = Set.new
- @dep_stack.each_value do |deps|
- all_deps.merge(deps)
- end
- all_deps.to_a
- end
-
- def all_specs
- @spec_stack.map do |path,spec|
- spec
- end
- end
-
- def dump(level = Logger::DEBUG)
- logger.add level, "v" * 80
- logger.add level, "path: #{@path.inspect}"
- logger.add level, "deps: (#{deps.size})"
- deps.map do |dep|
- logger.add level, gem_resolver_inspect(dep)
- end
- logger.add level, "remaining_deps: (#{remaining_deps.size})"
- remaining_deps.each do |dep|
- logger.add level, gem_resolver_inspect(dep)
- end
- logger.add level, "dep_stack: "
- @dep_stack.each do |path,deps|
- logger.add level, "#{path.inspect} (#{deps.size})"
- deps.each do |dep|
- logger.add level, "-> #{gem_resolver_inspect(dep)}"
- end
- end
- logger.add level, "spec_stack: "
- @spec_stack.each do |path,spec|
- logger.add level, "#{path.inspect}: #{gem_resolver_inspect(spec)}"
- end
- logger.add level, "^" * 80
- end
-
- def to_dot
- io = StringIO.new
- io.puts 'digraph deps {'
- io.puts ' fontname = "Courier";'
- io.puts ' mincross = 4.0;'
- io.puts ' ratio = "auto";'
- dump_to_dot(io, "<top>", [])
- io.puts '}'
- io.string
- end
-
- def dump_to_dot(io, name, path)
- @dep_stack[path].each_with_index do |dep,i|
- new_path = path + [i]
- spec_name = all_specs.find {|x| x.name == dep.name}.full_name
- io.puts ' "%s" -> "%s";' % [name, dep.to_s]
- io.puts ' "%s" -> "%s";' % [dep.to_s, spec_name]
- if @spec_stack.key?(new_path)
- dump_to_dot(io, spec_name, new_path)
- end
- end
- end
- end
- end
-end \ No newline at end of file
diff --git a/spec/builders.rb b/spec/builders.rb
new file mode 100644
index 0000000000..f13a9594f8
--- /dev/null
+++ b/spec/builders.rb
@@ -0,0 +1,59 @@
+module Spec
+ module Builders
+ def build_index(&block)
+ index = Gem::SourceIndex.new
+ IndexBuilder.run(index, &block) if block_given?
+ index
+ end
+
+ def build_spec(name, version, &block)
+ spec = Gem::Specification.new
+ spec.instance_variable_set(:@name, name)
+ spec.instance_variable_set(:@version, Gem::Version.new(version))
+ DepBuilder.run(spec, &block) if block_given?
+ spec
+ end
+
+ def build_dep(name, requirements, type = :runtime)
+ Gem::Dependency.new(name, requirements, type)
+ end
+
+ class IndexBuilder
+ include Builders
+
+ def self.run(index, &block)
+ new(index).run(&block)
+ end
+
+ def initialize(index)
+ @index = index
+ end
+
+ def run(&block)
+ instance_eval(&block)
+ end
+
+ def add_spec(*args, &block)
+ @index.add_spec(build_spec(*args, &block))
+ end
+ end
+
+ class DepBuilder
+ def self.run(spec, &block)
+ new(spec).run(&block)
+ end
+
+ def initialize(spec)
+ @spec = spec
+ end
+
+ def run(&block)
+ instance_eval(&block)
+ end
+
+ def runtime(name, requirements)
+ @spec.add_runtime_dependency(name, requirements)
+ end
+ end
+ end
+end \ No newline at end of file
diff --git a/spec/resolver/engine_spec.rb b/spec/resolver/engine_spec.rb
index e519a0e61c..e7d0f1953e 100644
--- a/spec/resolver/engine_spec.rb
+++ b/spec/resolver/engine_spec.rb
@@ -11,7 +11,7 @@ describe "Resolving specs" do
]
solution = Bundler::Resolver.resolve(deps, index)
- solution.all_specs.should match_gems(
+ solution.should match_gems(
"bar" => ["2.0.0"]
)
end
@@ -34,7 +34,7 @@ describe "Resolving specs" do
]
solution = Bundler::Resolver.resolve(deps, index)
- solution.all_specs.should match_gems(
+ solution.should match_gems(
"activemerchant" => ["1.4.1"],
"action_pack" => ["2.3.2"],
"activesupport" => ["2.3.2"]
@@ -54,7 +54,7 @@ describe "Resolving specs" do
]
solution = Bundler::Resolver.resolve(deps, index)
- solution.all_specs.should match_gems(
+ solution.should match_gems(
"bar" => ["2.0.0"],
"foo" => ["1.1"]
)
@@ -78,7 +78,7 @@ describe "Resolving specs" do
]
solution = Bundler::Resolver.resolve(deps, index)
- solution.all_specs.should match_gems(
+ solution.should match_gems(
"bar" => ["1.0"],
"foo" => ["1.0"]
)
@@ -92,7 +92,7 @@ describe "Resolving specs" do
]
solution = Bundler::Resolver.resolve(deps, index)
- solution.all_specs.should match_gems(
+ solution.should match_gems(
"merb-core"=>["1.0.7.1"],
"rake"=>["0.8.7"],
"thor"=>["0.9.9"],
diff --git a/spec/spec_helper.rb b/spec/spec_helper.rb
index 902900ff48..b0b49ecbcd 100644
--- a/spec/spec_helper.rb
+++ b/spec/spec_helper.rb
@@ -1,7 +1,7 @@
$:.unshift File.join(File.dirname(__FILE__), '..', 'lib')
$:.push File.join(File.dirname(__FILE__))
require "bundler"
-require "bundler/resolver/builders"
+require "builders"
require "matchers"
require "pathname"
require "pp"
@@ -81,7 +81,7 @@ module Spec
end
Spec::Runner.configure do |config|
- config.include Bundler::Resolver::Builders
+ config.include Spec::Builders
config.include Spec::Matchers
config.include Spec::Helpers
View Lorry Controller Status