diff options
Diffstat (limited to 'lib/bundler')
-rw-r--r-- | lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo.rb (renamed from lib/bundler/vendor/Molinillo-master/lib/molinillo.rb) | 0 | ||||
-rw-r--r-- | lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/dependency_graph.rb (renamed from lib/bundler/vendor/Molinillo-master/lib/molinillo/dependency_graph.rb) | 2 | ||||
-rw-r--r-- | lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/errors.rb (renamed from lib/bundler/vendor/Molinillo-master/lib/molinillo/errors.rb) | 0 | ||||
-rw-r--r-- | lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/gem_metadata.rb (renamed from lib/bundler/vendor/Molinillo-master/lib/molinillo/gem_metadata.rb) | 0 | ||||
-rw-r--r-- | lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/modules/specification_provider.rb (renamed from lib/bundler/vendor/Molinillo-master/lib/molinillo/modules/specification_provider.rb) | 0 | ||||
-rw-r--r-- | lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/modules/ui.rb (renamed from lib/bundler/vendor/Molinillo-master/lib/molinillo/modules/ui.rb) | 0 | ||||
-rw-r--r-- | lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/resolution.rb (renamed from lib/bundler/vendor/Molinillo-master/lib/molinillo/resolution.rb) | 149 | ||||
-rw-r--r-- | lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/resolver.rb (renamed from lib/bundler/vendor/Molinillo-master/lib/molinillo/resolver.rb) | 0 | ||||
-rw-r--r-- | lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/state.rb (renamed from lib/bundler/vendor/Molinillo-master/lib/molinillo/state.rb) | 0 | ||||
-rw-r--r-- | lib/bundler/vendored_molinillo.rb | 2 |
10 files changed, 134 insertions, 19 deletions
diff --git a/lib/bundler/vendor/Molinillo-master/lib/molinillo.rb b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo.rb index bf740e48..bf740e48 100644 --- a/lib/bundler/vendor/Molinillo-master/lib/molinillo.rb +++ b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo.rb diff --git a/lib/bundler/vendor/Molinillo-master/lib/molinillo/dependency_graph.rb b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/dependency_graph.rb index 53e09ac7..9679222a 100644 --- a/lib/bundler/vendor/Molinillo-master/lib/molinillo/dependency_graph.rb +++ b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/dependency_graph.rb @@ -162,7 +162,7 @@ module Bundler::Molinillo # @return [Array<Object>] all of the requirements that required # this vertex def requirements - incoming_edges.flat_map(&:requirements) + explicit_requirements + (incoming_edges.map(&:requirements) + explicit_requirements).flatten end # @return [Array<Edge>] the edges of {#graph} that have `self` as their diff --git a/lib/bundler/vendor/Molinillo-master/lib/molinillo/errors.rb b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/errors.rb index b828d0c2..b828d0c2 100644 --- a/lib/bundler/vendor/Molinillo-master/lib/molinillo/errors.rb +++ b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/errors.rb diff --git a/lib/bundler/vendor/Molinillo-master/lib/molinillo/gem_metadata.rb b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/gem_metadata.rb index 7c5a03fa..7c5a03fa 100644 --- a/lib/bundler/vendor/Molinillo-master/lib/molinillo/gem_metadata.rb +++ b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/gem_metadata.rb diff --git a/lib/bundler/vendor/Molinillo-master/lib/molinillo/modules/specification_provider.rb b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/modules/specification_provider.rb index 79a85e77..79a85e77 100644 --- a/lib/bundler/vendor/Molinillo-master/lib/molinillo/modules/specification_provider.rb +++ b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/modules/specification_provider.rb diff --git a/lib/bundler/vendor/Molinillo-master/lib/molinillo/modules/ui.rb b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/modules/ui.rb index fce3290d..fce3290d 100644 --- a/lib/bundler/vendor/Molinillo-master/lib/molinillo/modules/ui.rb +++ b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/modules/ui.rb diff --git a/lib/bundler/vendor/Molinillo-master/lib/molinillo/resolution.rb b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/resolution.rb index a3f27253..743b1629 100644 --- a/lib/bundler/vendor/Molinillo-master/lib/molinillo/resolution.rb +++ b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/resolution.rb @@ -9,11 +9,16 @@ module Bundler::Molinillo # 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 + :possibility, + :locked_requirement, + :requirement_trees ) # @return [SpecificationProvider] the provider that knows about @@ -43,6 +48,7 @@ module Bundler::Molinillo @base = base @states = [] @iteration_counter = 0 + @all_conflicts = [] end # Resolves the {#original_requested} dependencies into a full dependency @@ -57,12 +63,14 @@ module Bundler::Molinillo 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)" } + 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 @@ -106,6 +114,10 @@ module Bundler::Molinillo # @return [Array<ResolutionState>] the stack of states for the resolution attr_accessor :states + # @return [Array<Array(String,Object)>] 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) @@ -174,9 +186,9 @@ module Bundler::Molinillo # 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) - states.pop if state + states.slice!((state_index_for_unwind + 1)..-1) raise VersionConflict.new(c) unless state state.conflicts = c end @@ -185,35 +197,137 @@ module Bundler::Molinillo # @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) - ) + 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 - index + 2 + 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) - 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) } + all_conflicts << [name, vertex.payload] conflicts[name] = Conflict.new( requirement, Hash[requirements.select { |_, r| !r.empty? }], - existing, - possibility + vertex.payload, + possibility, + locked_requirement_named(name), + requirement_trees ) end + # @return [Array<Array<Object>>] 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<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 @@ -243,7 +357,8 @@ module Bundler::Molinillo def attempt_to_activate debug(depth) { 'Attempting to activate ' + possibility.to_s } existing_node = activated.vertex_named(name) - if existing_node && existing_node.payload + 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 @@ -260,7 +375,7 @@ module Bundler::Molinillo push_state_for_requirements(new_requirements) else create_conflict - debug(depth) { 'Unsatisfied by existing spec' } + debug(depth) { "Unsatisfied by existing spec (#{existing_node.payload})" } unwind_for_conflict end end diff --git a/lib/bundler/vendor/Molinillo-master/lib/molinillo/resolver.rb b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/resolver.rb index 7cfe914d..7cfe914d 100644 --- a/lib/bundler/vendor/Molinillo-master/lib/molinillo/resolver.rb +++ b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/resolver.rb diff --git a/lib/bundler/vendor/Molinillo-master/lib/molinillo/state.rb b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/state.rb index 8e394f86..8e394f86 100644 --- a/lib/bundler/vendor/Molinillo-master/lib/molinillo/state.rb +++ b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/state.rb 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' |