class Solve::GecodeSolver

Attributes

demands_array[R]

@example Demands are Arrays of Arrays with an artifact name and optional constraint:

[['nginx', '= 1.0.0'], ['mysql']]

@return [Array<String>, Array<Array<String, String>>] demands

ds_graph[R]

DepSelector::DependencyGraph object representing the problem.

graph[R]

Graph object with references to all known artifacts and dependency constraints.

@return [Solve::Graph]

timeout_ms[R]

Timeout in milliseconds. Hardcoded to 1s for now.

Public Class Methods

activate() click to toggle source

Attemp to load the dep_selector gem which this solver engine requires.

# File lib/solve/gecode_solver.rb, line 18
def activate
  require "dep_selector"
rescue LoadError => e
  raise Errors::EngineNotAvailable, "dep_selector is not installed, GecodeSolver cannot be used (#{e})"
end
new(graph, demands, options = {}) click to toggle source

@example Basic use:

graph = Solve::Graph.new
graph.artifacts("mysql", "1.2.0")
demands = [["mysql"]]
GecodeSolver.new(graph, demands)

@param [Solve::Graph] graph @param [Array<String>, Array<Array<String, String>>] demands @param [Hash] options - unused, only present for API compatibility with RubySolver

# File lib/solve/gecode_solver.rb, line 44
def initialize(graph, demands, options = {})
  @ds_graph      = DepSelector::DependencyGraph.new
  @graph         = graph
  @demands_array = demands
  @timeout_ms    = self.class.timeout
end
timeout() click to toggle source

The timeout (in seconds) to use when resolving graphs. Default is 10. This can be configured by setting the SOLVE_TIMEOUT environment variable.

@return [Integer]

# File lib/solve/gecode_solver.rb, line 12
def timeout
  seconds = 30 unless ( seconds = ENV["SOLVE_TIMEOUT"] )
  seconds.to_i * 1_000
end

Public Instance Methods

demands() click to toggle source

The problem demands given as Demand model objects @return [Array<Solve::Demand>]

# File lib/solve/gecode_solver.rb, line 53
def demands
  demands_array.map do |name, constraint|
    Demand.new(self, name, constraint)
  end
end
resolve(options = {}) click to toggle source

@option options [Boolean] :sorted

return the solution as a sorted list instead of a Hash

@return [Hash, List] Returns a hash like { “Artifact Name” => “Version”,… }

unless the :sorted option is true, then it returns a list like [["Artifact Name", "Version],...]

@raise [Errors::NoSolutionError] when the demands cannot be met for the

given graph.

@raise [Errors::UnsortableSolutionError] when the :sorted option is true

and the demands have a solution, but the solution contains a cyclic
dependency
# File lib/solve/gecode_solver.rb, line 69
def resolve(options = {})
  solution = solve_demands(demands_as_constraints)

  unsorted_solution = solution.inject({}) do |stringified_soln, (name, version)|
    stringified_soln[name] = version.to_s
    stringified_soln
  end

  if options[:sorted]
    build_sorted_solution(unsorted_solution)
  else
    unsorted_solution
  end
end

Private Instance Methods

add_artifact_to_ds_graph(artifact) click to toggle source
# File lib/solve/gecode_solver.rb, line 145
def add_artifact_to_ds_graph(artifact)
  package_version = ds_graph.package(artifact.name).add_version(artifact.version)
  artifact.dependencies.each do |dependency|
    dependency = DepSelector::Dependency.new(ds_graph.package(dependency.name), dependency.constraint)
    package_version.dependencies << dependency
  end
  package_version
end
all_artifacts() click to toggle source

Maps all artifacts in the graph to DepSelector::Package objects. If not already done, artifacts are added to the ds_graph as a necessary side effect.

# File lib/solve/gecode_solver.rb, line 126
def all_artifacts
  return @all_artifacts if @all_artifacts

  populate_ds_graph!
  @all_artifacts
end
build_sorted_solution(unsorted_solution) click to toggle source
# File lib/solve/gecode_solver.rb, line 187
def build_sorted_solution(unsorted_solution)
  nodes = {}
  unsorted_solution.each do |name, version|
    nodes[name] = @graph.artifact(name, version).dependencies.map(&:name)
  end

  # Modified from http://ruby-doc.org/stdlib-1.9.3/libdoc/tsort/rdoc/TSort.html
  class << nodes
    include TSort
    alias tsort_each_node each_key
    def tsort_each_child(node, &block)
      fetch(node).each(&block)
    end
  end
  begin
    sorted_names = nodes.tsort
  rescue TSort::Cyclic => e
    raise Solve::Errors::UnsortableSolutionError.new(e, unsorted_solution)
  end

  sorted_names.map do |artifact|
    [artifact, unsorted_solution[artifact]]
  end
end
demands_as_constraints() click to toggle source

Maps demands to corresponding DepSelector::SolutionConstraint objects.

# File lib/solve/gecode_solver.rb, line 116
def demands_as_constraints
  @demands_as_constraints ||= demands_array.map do |demands_item|
    item_name, constraint_with_operator = demands_item
    version_constraint = Semverse::Constraint.new(constraint_with_operator)
    DepSelector::SolutionConstraint.new(ds_graph.package(item_name), version_constraint)
  end
end
populate_ds_graph!() click to toggle source

Converts artifacts to DepSelector::Package objects and adds them to the DepSelector graph. This should only be called once; use all_artifacts to safely get the set of all artifacts.

# File lib/solve/gecode_solver.rb, line 136
def populate_ds_graph!
  @all_artifacts = Set.new

  graph.artifacts.each do |artifact|
    add_artifact_to_ds_graph(artifact)
    @all_artifacts << ds_graph.package(artifact.name)
  end
end
report_invalid_constraints_error(e) click to toggle source
# File lib/solve/gecode_solver.rb, line 154
def report_invalid_constraints_error(e)
  non_existent_cookbooks = e.non_existent_packages.inject([]) do |list, constraint|
    list << constraint.package.name
  end

  constrained_to_no_versions = e.constrained_to_no_versions.inject([]) do |list, constraint|
    list << [constraint.package.name, constraint.constraint.to_s]
  end

  raise Solve::Errors::NoSolutionError.new(
    "Required artifacts do not exist at the desired version",
    missing_artifacts: non_existent_cookbooks,
    constraints_excluding_all_artifacts: constrained_to_no_versions
  )
end
report_no_solution_error(e) click to toggle source
# File lib/solve/gecode_solver.rb, line 170
def report_no_solution_error(e)
  most_constrained_cookbooks = e.disabled_most_constrained_packages.inject([]) do |list, package|
    list << "#{package.name} = #{package.versions.first}"
  end

  non_existent_cookbooks = e.disabled_non_existent_packages.inject([]) do |list, package|
    list << package.name
  end

  raise Solve::Errors::NoSolutionError.new(
    e.message,
    unsatisfiable_demand: e.unsatisfiable_solution_constraint.to_s,
    missing_artifacts: non_existent_cookbooks,
    artifacts_with_no_satisfactory_version: most_constrained_cookbooks
  )
end
solve_demands(demands_as_constraints) click to toggle source

Runs the solver with the set of demands given. If any DepSelector exceptions are raised, they are rescued and re-raised

# File lib/solve/gecode_solver.rb, line 94
def solve_demands(demands_as_constraints)
  selector = DepSelector::Selector.new(ds_graph, (timeout_ms / 1000.0))
  selector.find_solution(demands_as_constraints, all_artifacts)
rescue DepSelector::Exceptions::InvalidSolutionConstraints => e
  report_invalid_constraints_error(e)
rescue DepSelector::Exceptions::NoSolutionExists => e
  report_no_solution_error(e)
rescue DepSelector::Exceptions::TimeBoundExceeded
  # DepSelector timed out trying to find the solution. There may or may
  # not be a solution.
  raise Solve::Errors::NoSolutionError.new(
    "The dependency constraints could not be solved in the time allotted."
  )
rescue DepSelector::Exceptions::TimeBoundExceededNoSolution
  # DepSelector determined there wasn't a solution to the problem, then
  # timed out trying to determine which constraints cause the conflict.
  raise Solve::Errors::NoSolutionCauseUnknown.new(
    "There is a dependency conflict, but the solver could not determine the precise cause in the time allotted."
  )
end