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



123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
 
# File 'lib/grimoire/solver.rb', line 123

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) 


145
146
147
148
149
150
151
 
# File 'lib/grimoire/solver.rb', line 145

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>) 


286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
 
# File 'lib/grimoire/solver.rb', line 286

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) 


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

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
 
# 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].delete_if do |r_unit|
      unless(req.requirement.satisfied_by?(r_unit.version))
        debug "Pruning unit due to root requirement satisfaction failure - #{req.name}: #{req.requirement} not satisfied by #{r_unit.name} @ #{r_unit.version}"
        true
      end
    end
  end
  requirements.requirements.each do |req|
    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
  missing_new_world = requirements.requirements.find_all do |req|
    new_world.units[req.name].nil? || new_world.units[req.name].empty?
  end
  unless(missing_new_world.empty?)
    missed_units = missing_new_world.map(&:name).sort
    raise Error::NoSolution.new "Failed to satisfy core requirements (#{missed_units.join(', ')})"
  end
  @world = new_world
  @new_world = nil
  self
end

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

Returns:

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


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

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) 


197
198
199
200
201
202
203
204
 
# File 'lib/grimoire/solver.rb', line 197

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:



234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
 
# File 'lib/grimoire/solver.rb', line 234

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_collection = deps.find_all do |d|
          d.name == u_dep.name
        end
        existing_requirements = deps.map do |d|
          d.dependencies.find_all do |d_dep|
            d_dep.name == u_dep.name
          end
        end.flatten.compact.map(&:requirement)
        existing_collection.each do |existing|
          ([u_dep.requirement] + existing_requirements).each do |req|
            unless(req.satisfied_by?(existing.version))
              deps.delete(existing)
              reset_queue(u_dep.name)
              raise Error::ResolutionPathInvalid.new("Unit <#{existing.inspect}> does not satisfy <#{req.inspect}>")
            end
          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



185
186
187
188
189
190
191
 
# File 'lib/grimoire/solver.rb', line 185

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:



211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
 
# File 'lib/grimoire/solver.rb', line 211

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