diff options
Diffstat (limited to 'lib/bundler/vendor/pub_grub/lib/pub_grub/partial_solution.rb')
-rw-r--r-- | lib/bundler/vendor/pub_grub/lib/pub_grub/partial_solution.rb | 121 |
1 files changed, 121 insertions, 0 deletions
diff --git a/lib/bundler/vendor/pub_grub/lib/pub_grub/partial_solution.rb b/lib/bundler/vendor/pub_grub/lib/pub_grub/partial_solution.rb new file mode 100644 index 0000000000..4c4b8ca844 --- /dev/null +++ b/lib/bundler/vendor/pub_grub/lib/pub_grub/partial_solution.rb @@ -0,0 +1,121 @@ +require_relative 'assignment' + +module Bundler::PubGrub + class PartialSolution + attr_reader :assignments, :decisions + attr_reader :attempted_solutions + + def initialize + reset! + + @attempted_solutions = 1 + @backtracking = false + end + + def decision_level + @decisions.length + end + + def relation(term) + package = term.package + return :overlap if !@terms.key?(package) + + @relation_cache[package][term] ||= + @terms[package].relation(term) + end + + def satisfies?(term) + relation(term) == :subset + end + + def derive(term, cause) + add_assignment(Assignment.new(term, cause, decision_level, assignments.length)) + end + + def satisfier(term) + assignment = + @assignments_by[term.package].bsearch do |assignment_by| + @cumulative_assignments[assignment_by].satisfies?(term) + end + + assignment || raise("#{term} unsatisfied") + end + + # A list of unsatisfied terms + def unsatisfied + @required.keys.reject do |package| + @decisions.key?(package) + end.map do |package| + @terms[package] + end + end + + def decide(package, version) + @attempted_solutions += 1 if @backtracking + @backtracking = false; + + decisions[package] = version + assignment = Assignment.decision(package, version, decision_level, assignments.length) + add_assignment(assignment) + end + + def backtrack(previous_level) + @backtracking = true + + new_assignments = assignments.select do |assignment| + assignment.decision_level <= previous_level + end + + new_decisions = Hash[decisions.first(previous_level)] + + reset! + + @decisions = new_decisions + + new_assignments.each do |assignment| + add_assignment(assignment) + end + end + + private + + def reset! + # { Array<Assignment> } + @assignments = [] + + # { Package => Array<Assignment> } + @assignments_by = Hash.new { |h,k| h[k] = [] } + @cumulative_assignments = {}.compare_by_identity + + # { Package => Package::Version } + @decisions = {} + + # { Package => Term } + @terms = {} + @relation_cache = Hash.new { |h,k| h[k] = {} } + + # { Package => Boolean } + @required = {} + end + + def add_assignment(assignment) + term = assignment.term + package = term.package + + @assignments << assignment + @assignments_by[package] << assignment + + @required[package] = true if term.positive? + + if @terms.key?(package) + old_term = @terms[package] + @terms[package] = old_term.intersect(term) + else + @terms[package] = term + end + @relation_cache[package].clear + + @cumulative_assignments[assignment] = @terms[package] + end + end +end |