solving.rb

require 'ricosat'
require 'net/https'

class DepSolver
  NotVariable = Struct.new :name, :number

  class Variable < NotVariable
    def initialize name, number
      @not = NotVariable.new name, -number
      super
    end

    def !@; @not; end
  end

  def initialize
    @sat = RicoSat.new
    @sat.enable_trace_generation
    @name_cache  = {}
    @index_cache = []
    @rules       = []
  end

  def variable name
    if @name_cache.key? name
      @var_cache[name]
    else
      var = Variable.new name, @sat.inc_max_var
      @name_cache[name] = var
      @index_cache[var.number] = var
      var
    end
  end

  def rule2 a, b
    @sat.add a.number
    @sat.add b.number
    @sat.add 0
  end

  def rule list
    list.each { |i| @sat.add(i.number) }
    @sat.add 0
  end

  def variables
    @sat.variables
  end

  def solve
    case @sat.solve(-1)
    when RicoSat::UNSATISFIABLE
      @sat.added_original_clauses.times do |i|
        if @sat.coreclause(i) == 1
          p :clause => @rules[i].zip(@rules[i].map { |r| @sat.corelit(r.number.abs) })
        end
      end
      :boo
    when RicoSat::SATISFIABLE
      variables.times.select { |i| @sat.deref(i + 1) }.map { |i|
        @index_cache[i + 1]
      }
    else
    end
  end
end

class InstallRequest
  def self.possible_gems_for name
    gems         = {}
    base_path    = '/api/v1/dependencies?gems='
    http         = Net::HTTP.new 'rubygems.org', 443
    http.use_ssl = true

    deps = [name]
    http.start do |client|
      loop do
        fetch = deps.reject { |dep| gems.key? dep }
        break if fetch.empty?

        path = base_path + fetch.join(',')
        res = client.request Net::HTTP::Get.new path
        gems_versions = Marshal.load(res.body)
        deps = gems_versions.flat_map { |gem| gem[:dependencies].map(&:first) }.uniq
        gems.merge! gems_versions.group_by { |gem| gem[:name] }
      end
    end
    gems
  end

  def self.fill_sat solver, gems
    gems = gems.transform_values do |versions|
      versions.map { |ver| solver.variable ver }
    end

    gems.each_pair do |gem_name, variables|
      # Only one version allowed
      variables.combination(2).each { |l,r| solver.rule2(!l, !r) }

      variables.each do |variable|
        version = variable.name

        version[:dependencies].each do |name, version_spec|
          requirements = version_spec.split(', ').map { |v| Gem::Requirement.new v }

          next unless gems.key? name # dep doesn't exist

          deps         = gems[name].select { |dep_variable|
            dep_version = dep_variable.name
            requirements.all? { |req|
              req.satisfied_by? Gem::Version.new(dep_version[:number])
            }
          }
          solver.rule [!variable] + deps
        end
      end
    end
    solver
  end
end

p "downloading" => Time.now
gems = InstallRequest.possible_gems_for 'rails'
wanted = gems['rails'].find_all { |ver| ver[:number] == '5.0.1' }
solv = DepSolver.new
var = solv.variable wanted
solv.rule [var]
p "filling" => Time.now
solv = InstallRequest.fill_sat solv, gems
p "solving" => Time.now
solv.solve.map { |var|
  p var
}

exit

exit
a1, a2, a3 = *3.times.map { |i| solv.variable "A#{i + 1}" }
b1, b2, b3 = *3.times.map { |i| solv.variable "B#{i + 1}" }
c1, c2, c3 = *3.times.map { |i| solv.variable "C#{i + 1}" }
d1, d2, d3 = *3.times.map { |i| solv.variable "D#{i + 1}" }
e1, e2, e3 = *3.times.map { |i| solv.variable "E#{i + 1}" }

solv.rule [a3] # User requests Package A, version 3

solv.rule [!a3, b1, b2, b3] # Depends on B1, B2, or B3
solv.rule [!a3, c1, c2, c3] # ditto for C
solv.rule [!a3, e1, e2, e3] # ditto for E

solv.rule [!b1, d1, d2]     # B1 depends on D1 or D2

solv.rule [!b2, d1, d2]     # ditto for B2

solv.rule [!b3, d1, d2]     # ditto for B3

solv.rule [!c1, d3]

solv.rule [!c2, d2]

solv.rule [!c3, d1]

# Only one version of any package is allowed
[b1, b2, b3].combination(2) { |l,r| solv.rule [!l, !r] }
[c1, c2, c3].combination(2) { |l,r| solv.rule [!l, !r] }
[d1, d2, d3].combination(2) { |l,r| solv.rule [!l, !r] }
[e1, e2, e3].combination(2) { |l,r| solv.rule [!l, !r] }

p solv.variables
p solv.solve

__END__

[aaron@TC ricosat (master)]$ ruby -I lib test.rb
{"downloading"=>2017-02-19 13:08:49 -0800}
{"filling"=>2017-02-19 13:08:50 -0800}
{"solving"=>2017-02-19 13:09:37 -0800}
#<struct DepSolver::Variable name=[{:name=>"rails", :number=>"5.0.1", :platform=>"ruby", :dependencies=>[["sprockets-rails", ">= 2.0.0"], ["bundler", "< 2.0, >= 1.3.0"], ["railties", "= 5.0.1"], ["actioncable", "= 5.0.1"], ["activejob", "= 5.0.1"], ["actionmailer", "= 5.0.1"], ["activerecord", "= 5.0.1"], ["activemodel", "= 5.0.1"], ["actionview", "= 5.0.1"], ["actionpack", "= 5.0.1"], ["activesupport", "= 5.0.1"]]}], number=1>
#<struct DepSolver::Variable name={:name=>"builder", :number=>"2.1.2", :platform=>"ruby", :dependencies=>[]}, number=2970>
#<struct DepSolver::Variable name={:name=>"journey", :number=>"1.0.4", :platform=>"ruby", :dependencies=>[]}, number=3246>
#<struct DepSolver::Variable name={:name=>"erubis", :number=>"2.6.6", :platform=>"ruby", :dependencies=>[["abstract", ">= 1.0.0"]]}, number=3360>
#<struct DepSolver::Variable name={:name=>"rails-html-sanitizer", :number=>"1.0.1", :platform=>"ruby", :dependencies=>[["loofah", "~> 2.0"]]}, number=3426>
#<struct DepSolver::Variable name={:name=>"text-format", :number=>"1.0.0", :platform=>"ruby", :dependencies=>[["text-hyphen", "~> 1.0.0"]]}, number=3579>
#<struct DepSolver::Variable name={:name=>"thor", :number=>"0.14.6", :platform=>"ruby", :dependencies=>[]}, number=3590>
#<struct DepSolver::Variable name={:name=>"ref", :number=>"1.0.5", :platform=>"ruby", :dependencies=>[]}, number=4323>
#<struct DepSolver::Variable name={:name=>"abstract", :number=>"1.0.0", :platform=>"ruby", :dependencies=>[]}, number=4605>
#<struct DepSolver::Variable name={:name=>"multimap", :number=>"1.1.3", :platform=>"ruby", :dependencies=>[]}, number=4606>
#<struct DepSolver::Variable name={:name=>"nokogiri", :number=>"1.6.8", :platform=>"ruby", :dependencies=>[["pkg-config", "~> 1.1.7"], ["mini_portile2", "~> 2.1.0"]]}, number=4945>
#<struct DepSolver::Variable name={:name=>"loofah", :number=>"2.0.3", :platform=>"ruby", :dependencies=>[["nokogiri", ">= 1.5.9"]]}, number=4966>
#<struct DepSolver::Variable name={:name=>"tlsmail", :number=>"0.0.1", :platform=>"ruby", :dependencies=>[]}, number=5042>
#<struct DepSolver::Variable name={:name=>"text-hyphen", :number=>"1.0.2", :platform=>"ruby", :dependencies=>[]}, number=5047>
#<struct DepSolver::Variable name={:name=>"websocket-extensions", :number=>"0.1.0", :platform=>"ruby", :dependencies=>[]}, number=5049>
#<struct DepSolver::Variable name={:name=>"rspec-logsplit", :number=>"0.1.3", :platform=>"ruby", :dependencies=>[]}, number=5479>
#<struct DepSolver::Variable name={:name=>"metaid", :number=>"1.0", :platform=>"ruby", :dependencies=>[]}, number=5889>
#<struct DepSolver::Variable name={:name=>"gem_plugin", :number=>"0.2.3", :platform=>"ruby", :dependencies=>[]}, number=5928>
#<struct DepSolver::Variable name={:name=>"cgi_multipart_eof_fix", :number=>"2.5.0", :platform=>"ruby", :dependencies=>[]}, number=5935>
#<struct DepSolver::Variable name={:name=>"weakling", :number=>"0.0.3", :platform=>"ruby", :dependencies=>[]}, number=5994>
#<struct DepSolver::Variable name={:name=>"mini_portile", :number=>"0.6.0", :platform=>"ruby", :dependencies=>[]}, number=6005>
#<struct DepSolver::Variable name={:name=>"mini_portile2", :number=>"2.1.0", :platform=>"ruby", :dependencies=>[]}, number=6017>
#<struct DepSolver::Variable name={:name=>"pkg-config", :number=>"1.1.7", :platform=>"ruby", :dependencies=>[]}, number=6082>
#<struct DepSolver::Variable name={:name=>"tenderlove-frex", :number=>"1.0.1.20090313144615", :platform=>"ruby", :dependencies=>[]}, number=6087>
#<struct DepSolver::Variable name={:name=>"diff-lcs", :number=>"1.1.2", :platform=>"ruby", :dependencies=>[]}, number=6229>
#<struct DepSolver::Variable name={:name=>"win32-security", :number=>"0.2.5", :platform=>"ruby", :dependencies=>[["ffi", ">= 0"]]}, number=6777>
#<struct DepSolver::Variable name={:name=>"ffi", :number=>"1.9.10", :platform=>"ruby", :dependencies=>[]}, number=7018>
#<struct DepSolver::Variable name={:name=>"metaclass", :number=>"0.0.2", :platform=>"ruby", :dependencies=>[]}, number=7520>
#<struct DepSolver::Variable name={:name=>"multi_test", :number=>"0.1.1", :platform=>"ruby", :dependencies=>[]}, number=8113>
#<struct DepSolver::Variable name={:name=>"cucumber-wire", :number=>"0.0.1", :platform=>"ruby", :dependencies=>[]}, number=8138>
#<struct DepSolver::Variable name={:name=>"configuration", :number=>"0.0.5", :platform=>"ruby", :dependencies=>[]}, number=8150>
#<struct DepSolver::Variable name={:name=>"powerpack", :number=>"0.1.1", :platform=>"ruby", :dependencies=>[]}, number=8716>
#<struct DepSolver::Variable name={:name=>"trollop", :number=>"1.16.2", :platform=>"ruby", :dependencies=>[]}, number=9035>
#<struct DepSolver::Variable name={:name=>"little-plugger", :number=>"1.1.3", :platform=>"ruby", :dependencies=>[]}, number=9077>
#<struct DepSolver::Variable name={:name=>"ast", :number=>"2.2.0", :platform=>"ruby", :dependencies=>[]}, number=9214>
#<struct DepSolver::Variable name={:name=>"allison", :number=>"2.0.3", :platform=>"ruby", :dependencies=>[]}, number=9654>
#<struct DepSolver::Variable name={:name=>"termios", :number=>"0.9.4", :platform=>"ruby", :dependencies=>[]}, number=9670>