Class: Solve::Solver

Inherits:
Object
  • Object
show all
Defined in:
lib/solve/solver.rb,
lib/solve/solver/variable.rb,
lib/solve/solver/constraint_row.rb,
lib/solve/solver/variable_table.rb,
lib/solve/solver/constraint_table.rb

Overview

Author:

Defined Under Namespace

Classes: ConstraintRow, ConstraintTable, Variable, VariableTable

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(graph, demands = Array.new) ⇒ Solver

Returns a new instance of Solver.

Parameters:

  • graph (Solve::Graph)
  • demands (Array<String>, Array<Array<String, String>>) (defaults to: Array.new) 


72
73
74
75
76
77
78
79
80
81
82
83
 
# File 'lib/solve/solver.rb', line 72

def initialize(graph, demands = Array.new)
  @graph = graph
  @domain = Hash.new
  @demands = Hash.new
  @possible_values = Hash.new
  @constraint_table = ConstraintTable.new
  @variable_table = VariableTable.new

  Array(demands).each do |l_demand|
    demands(*l_demand)
  end
end

Instance Attribute Details

#constraint_table ⇒ Object (readonly)

Returns the value of attribute constraint_table.



67
68
69
 
# File 'lib/solve/solver.rb', line 67

def constraint_table
  @constraint_table
end

#domain ⇒ Object (readonly)

Returns the value of attribute domain.



65
66
67
 
# File 'lib/solve/solver.rb', line 65

def domain
  @domain
end

#graph ⇒ Solve::Graph (readonly)

The world as we know it

Returns:



63
64
65
 
# File 'lib/solve/solver.rb', line 63

def graph
  @graph
end

#possible_values ⇒ Object (readonly)

Returns the value of attribute possible_values.



68
69
70
 
# File 'lib/solve/solver.rb', line 68

def possible_values
  @possible_values
end

#variable_table ⇒ Object (readonly)

Returns the value of attribute variable_table.



66
67
68
 
# File 'lib/solve/solver.rb', line 66

def variable_table
  @variable_table
end

Class Method Details

.demand_key(demand) ⇒ Symbol

Create a key to identify a demand on a Solver.

Parameters:

Returns:

  • (Symbol)

Raises:

  • (NoSolutionError) 


17
18
19
 
# File 'lib/solve/solver.rb', line 17

def demand_key(demand)
  "#{demand.name}-#{demand.constraint}".to_sym
end

.satisfy_all(constraints, versions) ⇒ Array<Solve::Version>

Returns all of the versions which satisfy all of the given constraints

Parameters:

Returns:



27
28
29
30
31
32
33
34
35
36
37
38
39
 
# File 'lib/solve/solver.rb', line 27

def satisfy_all(constraints, versions)
  constraints = Array(constraints).collect do |con|
    con.is_a?(Constraint) ? con : Constraint.new(con.to_s)
  end.uniq

  versions = Array(versions).collect do |ver|
    ver.is_a?(Version) ? ver : Version.new(ver.to_s)
  end.uniq

  versions.select do |ver|
    constraints.all? { |constraint| constraint.satisfies?(ver) }
  end
end

.satisfy_best(constraints, versions) ⇒ Solve::Version

Return the best version from the given list of versions for the given list of constraints

Parameters:

Returns:

Raises:

  • (NoSolutionError) —

    if version matches the given constraints



49
50
51
52
53
54
55
56
57
 
# File 'lib/solve/solver.rb', line 49

def satisfy_best(constraints, versions)
  solution = satisfy_all(constraints, versions)

  if solution.empty?
    raise Errors::NoSolutionError
  end

  solution.sort.last
end

Instance Method Details

#add_demand(demand) ⇒ Solve::Demand Also known as: demand

Add a Solve::Demand to the collection of demands and return the added Solve::Demand. No change will be made if the demand is already a member of the collection.

Parameters:

Returns:



160
161
162
163
164
165
166
 
# File 'lib/solve/solver.rb', line 160

def add_demand(demand)
  unless has_demand?(demand)
    @demands[self.class.demand_key(demand)] = demand
  end

  demand
end

#demands(name, constraint) ⇒ Solve::Demand #demands(name) ⇒ Solve::Demand #demands ⇒ Array<Solve::Demand>

Overloads:



134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
 
# File 'lib/solve/solver.rb', line 134

def demands(*args)
  if args.empty?
    return demand_collection
  end
  if args.length > 2
    raise ArgumentError, "Unexpected number of arguments. You gave: #{args.length}. Expected: 2 or less."
  end

  name, constraint = args
  constraint ||= ">= 0.0.0"

  if name.nil?
    raise ArgumentError, "A name must be specified. You gave: #{args}."
  end

  demand = Demand.new(self, name, constraint)
  add_demand(demand)
end

#has_demand?(demand) ⇒ Boolean

Parameters:

Returns:

  • (Boolean) 


179
180
181
 
# File 'lib/solve/solver.rb', line 179

def has_demand?(demand)
  @demands.has_key?(self.class.demand_key(demand))
end

#remove_demand(demand) ⇒ Object

Parameters:



170
171
172
173
174
 
# File 'lib/solve/solver.rb', line 170

def remove_demand(demand)
  if has_demand?(demand)
    @demands.delete(self.class.demand_key(demand))
  end
end

#resolve ⇒ Hash

Returns:

  • (Hash) 


86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
 
# File 'lib/solve/solver.rb', line 86

def resolve
  seed_demand_dependencies

  while unbound_variable = variable_table.first_unbound
    possible_values_for_unbound = possible_values_for(unbound_variable)
    
    while possible_value = possible_values_for_unbound.shift
      possible_artifact = graph.get_artifact(unbound_variable.package, possible_value.version)
      possible_dependencies = possible_artifact.dependencies
      all_ok = possible_dependencies.all? { |dependency| can_add_new_constraint?(dependency) }
      if all_ok
        add_dependencies(possible_dependencies, possible_artifact) 
        unbound_variable.bind(possible_value)
        break
      end
    end

    unless unbound_variable.bound?
      backtrack(unbound_variable) 
    end
  end

  {}.tap do |solution|
    variable_table.rows.each do |variable|
      solution[variable.package] = variable.value.version.to_s
    end
  end
end