Class: Grimoire::Solver

Inherits:
Utility show all
Includes:
Bogo::Memoization
Defined in:
lib/grimoire/solver.rb

Overview

Requirement solver

Constant Summary collapse

MAX_GENERATION_LOOPS =

Ceiling for number of loops allowed during path generation

100000

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods inherited from Utility

#debug, #to_json

Constructor Details

#initialize(*_) ⇒ Solver

Returns a new instance of Solver.



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

def initialize(*_)
  super
  @world = System.new
  @new_world = nil
  @log = []
  if(restrictions)
    apply_restrictions!
  end
  build_world(requirements.requirements, world, system)
  @log.clear
  world.scrub!
end

Instance Attribute Details

#new_world ⇒ System, NilClass (readonly)

Returns new system subset when pruning.

Returns:

  • (System, NilClass) —

    new system subset when pruning



26
27
28
 
# File 'lib/grimoire/solver.rb', line 26

def new_world
  @new_world
end

#world ⇒ System (readonly)

Returns subset of full system based on requirements.

Returns:

  • (System) —

    subset of full system based on requirements



24
25
26
 
# File 'lib/grimoire/solver.rb', line 24

def world
  @world
end

Instance Method Details

#apply_restrictions! ⇒ self

Restrictions are simply an implicit expansion of the requirements that. When restrictions are provided, it serves to further restrict the valid units available for solutions

Returns:

  • (self) 


46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
 
# File 'lib/grimoire/solver.rb', line 46

def apply_restrictions!
  restrictions.requirements.each do |rst|
    req = requirements.requirements.detect do |r|
      r.name == rst.name
    end
    if(req)
      new_req = req.merge(rst)
      requirements.requirements.delete(req)
      requirements.requirements.push(new_req)
    else
      requirements.requirements.push(rst)
    end
  end
  self
end

#build_world(deps = nil, my_world = nil, root = nil) ⇒ Object

Build the world required for the solver (the subset of the entire system required by the requirements)

Parameters:

  • deps (DEPENDENCY_CLASS) (defaults to: nil) —

    dependencies required to resolve

  • my_world (System) (defaults to: nil) —

    system to populate with units

  • root (System) (defaults to: nil) —

    superset system to extract units



108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
 
# File 'lib/grimoire/solver.rb', line 108

def build_world(deps=nil, my_world=nil, root = nil)
  deps = requirement.requirements unless deps
  my_world = world unless my_world
  root = system unless root
  deps.each do |dep|
    units = root.subset(dep.name, dep.requirement)
    sha = Digest::SHA256.hexdigest(MultiJson.dump(units))
    if(@log.include?(sha))
      debug "Units checksum already added to world. Skipping. (`#{sha}`)"
      next
    end
    debug "Logging units checksum for world addition. (`#{sha}`)"
    @log.push(sha)
    units.each do |unit|
      build_world(unit.dependencies, my_world, root)
    end
    debug "Units added to world: #{MultiJson.dump(units.map{|u| {u.name => u.version} })}"
    my_world.add_unit(units)
  end
end

#create_queue ⇒ Bogo::PriorityQueue

Returns:

  • (Bogo::PriorityQueue) 


130
131
132
133
134
135
136
 
# File 'lib/grimoire/solver.rb', line 130

def create_queue
  if(score_keeper)
    Bogo::PriorityQueue.new(score_keeper.preferred_score)
  else
    Bogo::PriorityQueue.new
  end
end

#generate! ⇒ Bogo::PriorityQueue<Path>

Generate valid constraint paths

Returns:

  • (Bogo::PriorityQueue<Path>) 


262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
 
# File 'lib/grimoire/solver.rb', line 262

def generate!
  if(requirements.requirements.empty?)
    raise ArgumentError.new 'No cookbook constraints provided within Batali file!'
  end
  custom_unit = Unit.new(
    :name => '~_SOLVER_UNIT_~',
    :version => '1.0.0',
    :dependencies => requirements.requirements
  )
  count = 0
  debug "Solver Unit: #{MultiJson.dump(custom_unit)}"
  debug{ "Solver world context of unit system: #{world.inspect}" }
  results = Bogo::PriorityQueue.new
  begin
    until(count >= result_limit)
      result = resolve(nil, custom_unit)
      results.push(Path.new(:units => result.slice(1, result.size)), count)
      count += 1
    end
  rescue Error::UnitUnavailable => e
    debug "Failed to locate unit: #{e}"
    count = nil
  end
  if(results.empty?)
    raise Error::NoSolution.new("Failed to generate valid path for requirements: `#{custom_unit.dependencies}`")
  else
    results
  end
end

#populate_queue(p_queue, units) ⇒ Bogo::PriorityQueue

Populate queue with units

Parameters:

  • p_queue (Bogo::PriorityQueue)
  • units (Array<Unit>)

Returns:

  • (Bogo::PriorityQueue) 


156
157
158
159
160
161
162
163
 
# File 'lib/grimoire/solver.rb', line 156

def populate_queue(p_queue, units)
  i = 0
  units = units.map do |unit|
    [unit, score_unit(unit, i += 1)]
  end
  p_queue.multi_push(units)
  p_queue
end

#prune_world! ⇒ self

Note:

This must be called explicitly and is provided for resolving an entire system, not a single resolution path

After the world has been generated extraneous units will be included as a result of dependency constraints that may be too loose and are not actually required by any resolution that would be requested. This will run a second pass and remove extraneous items not required.

Returns:

  • (self) 


71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
 
# File 'lib/grimoire/solver.rb', line 71

def prune_world!
  @new_world = System.new
  requirements.requirements.each do |req|
    unless(world.units[req.name])
      debug "No units available matching requirement name `#{req.name}`! (#{req.inspect})"
      exception = Error::UnitUnavailable.new "No units available for requirement `#{req.name}`"
      exception.unit_name = req.name
      raise exception
    end
    world.units[req.name].each do |r_unit|
      begin
        req_list = RequirementList.new(
          :name => :world_pruner,
          :requirements => [[r_unit.name, r_unit.version.version]]
        )
        path = Solver.new(
          :requirements => req_list,
          :system => world,
          :score_keeper => score_keeper
        ).generate!.pop
        new_world.add_unit(*path.units)
      rescue Error::NoSolution => e
        debug "Failed to generate valid path for: #{r_unit.name}-#{r_unit.version}"
      end
    end
  end
  @world = new_world
  @new_world = nil
  self
end

#queues ⇒ Smash<{Unit#name:Bogo::PriorityQueue}>

Returns:

  • (Smash<{Unit#name:Bogo::PriorityQueue}>) 


139
140
141
142
143
144
145
146
147
148
149
 
# File 'lib/grimoire/solver.rb', line 139

def queues
  memoize(:queues) do
    Smash[
      world.units.map do |name, items|
        queue = create_queue
        populate_queue(queue, items)
        [name, queue]
      end
    ]
  end
end

#reset_queue(name) ⇒ self

Repopulate the given queue

Parameters:

  • name (String)

Returns:

  • (self) 


182
183
184
185
186
187
188
189
 
# File 'lib/grimoire/solver.rb', line 182

def reset_queue(name)
  queue = populate_queue(
    create_queue,
    world.units.fetch(name, [])
  )
  queues[name] = queue
  self
end

#resolve(dep, given = nil, current = []) ⇒ Array<Unit>

Resolve path for a given dependency

Parameters:

Returns:



219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
 
# File 'lib/grimoire/solver.rb', line 219

def resolve(dep, given=nil, current=[])
  unit = given || unit_for(dep)
  if(unit.dependencies.empty?)
    [unit]
  else
    deps = [unit]
    begin
      unit.dependencies.map do |u_dep|
        existing = (current + deps).detect{|d| d.name == u_dep.name}
        if(existing)
          if(u_dep.requirement.satisfied_by?(existing.version))
            next
          else
            deps.delete(existing)
            reset_queue(u_dep.name) unless given
          end
        else
          reset_queue(u_dep.name) unless given
        end
        deps += resolve(u_dep, nil, current + deps)
        deps.compact!
        u_dep
      end.compact.map do |u_dep|  # validator
        existing = deps.detect{|d| d.name == u_dep.name}
        if(existing)
          unless(u_dep.requirement.satisfied_by?(existing.version))
            deps.delete(existing)
            reset_queue(u_dep.name)
            raise Error::ResolutionPathInvalid.new("Unit <#{existing.inspect}> does not satisfy <#{u_dep.inspect}>")
          end
        end
      end
    rescue Error::ResolutionPathInvalid => e
      debug "Resolution path deadend: #{e} (trying new path)"
      retry
    end
    deps.uniq
  end
end

#score_unit(unit, score) ⇒ Numeric

Provide score for given unit

Parameters:

  • unit (Unit)
  • score (Integer) —

    current score

Returns:

  • (Numeric) —

    score



170
171
172
173
174
175
176
 
# File 'lib/grimoire/solver.rb', line 170

def score_unit(unit, score)
  if(score_keeper)
    score_keeper.score_for(unit, score, :solver => self) || score
  else
    score
  end
end

#unit_for(dep) ⇒ Unit

Provide Unit acceptable for given dependency

Parameters:

Returns:



196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
 
# File 'lib/grimoire/solver.rb', line 196

def unit_for(dep)
  unit = nil
  if(queues[dep.name].nil?)
    raise KeyError.new "No valid units for requested name found within system! (`#{dep.name}`)"
  end
  until(unit || queues[dep.name].empty?)
    unit = queues[dep.name].pop
    unit = nil unless dep.requirement.satisfied_by?(unit.version)
  end
  unless(unit)
    error = Error::UnitUnavailable.new("Failed to locate valid unit for: #{dep.inspect}")
    error.unit_name = dep.name
    raise error
  end
  unit
end